Binary Search is a searching algorithm in data structure in which repeatedly the array is divided into half until the element to be searched is found.
For Example:
If we want to search 30 in the following Array:
Step-1: Firstly the array is of 5 elements then it is divided by 2 that is 5/2 means 3 element is compared firstly.
Step-2 : 30 is the third element then it is compared with the element to searched.
Step -3: It is matched then the element is found.
Advantages of Binary Search Over Linear Search
- Best for large amount of data.
- At each step the array is divided into half reduces space complexity
- Faster than Linear Search.
Disadvantage
- Can only be used for sorted array.
- Applicable on only single dimensional array .
- complicated than linear search.
Applications on Binary Search in real life
- Dictionary.
- Figure out resource requirement in larger system.
- Finding numerical solutions to the equations.
Binary Search Program in C++ Using Array
Group of element in any form of data structure is an array.
Program to search a number in c++ using array is as follows:
//To perform binary search//
#include<iostream>
using namespace std;
int main()
{
int ar[10]={10,20,30,40,50,60,70,80,90,100};
int lb,ub,mid,data,found;
char z;
cout<<"you want to enter array(y/n)\n";
cin>>z;
if(z=='y') {
cout<<"enter 10 ementnts (assending order) for array\n";
for(int i=0;i<10;i++)
cin>>ar[i];
}
if(z=='n') {
cout<<"your array\n";
for(int i=0;i<10;i++)
cout<<ar[i]<<"\t";
}
cout<<"\nenter data to search\n";
cin>>data;
lb=0;
ub=9;
mid=(lb+ub)/2;
found=0;
while((found==0) && (lb<=ub)) {
cout<<"while loop begin:\t"<<"lb:"<<lb<<"\tub:"<<ub<<"\tmid:"<<mid<<"\n";
if(ar[mid]==data){
found=1;
break;
}
if(ar[mid]>data)
ub=mid-1;
if(ar[mid]<data)
lb=mid+1;
mid=(lb+ub)/2;
cout<<"while loop end:\t\t"<<"lb:"<<lb<<"\tub:"<<ub<<"\tmid:"<<mid<<"\n";
}
cout<<"search element "<<data<<" is";
if(found==1)
cout<<" found at position "<<mid+1;
if(found==0)
cout<<" not found\n";
return 0;
}Output of the program in which number is to be searched using c++ in an array is as follows:
Binary Search Program in C++ Using Class
Binary Search Program in C++ Without Function
Program to search a number in c++ without function is as follows:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
int list[100];
int i,n,pos,x;
int first,middle,last;
char ch;
do{
cout<<"\n Enter the size of list: ";
cin>>n;
cout<<"\n Enter the Elements of the Array in Sorted order: \n";
for(i=0;i<n;i++){
cout<<" ";
cin>>list[i];
}
first=0;pos=-1;last=n-1;
cout<<"\n Enter the Value to be searched: ";
cin>>x;
//search the list.
while((first<=last)&&(pos==-1)){
middle=(first+last)/2;
if(list[middle]==x)
pos=middle;
else
if(list[middle]<x)
first=middle+1;
else
last=middle-1;
}
if(pos>-1)
cout<<"\n The Position of the element is: "<<++pos;
else
cout<<"\n Search Unsuccessfull!!\n";
cout<<"\nWant to continue(y/n):";
cin>>ch;
}while(ch=='y'||ch=='Y');
return 0;
}
Output of the program to be searched without function in c++ is as follows:
Binary Search in C
Program to search a element using c is as follows:
#include<stdio.h>
int main()
{
int list[100];
int i,n,pos,x;
int first,middle,last;
char ch;
do{
printf("\n Enter the size of list: ");
scanf("%d",&n);
printf("\n Enter the Elements of the Array in Sorted order: \n");
for(i=0;i<n;i++){
printf(" ");
scanf("%d",&list[i]);
}
first=0;pos=-1;last=n-1;
printf("\n Enter the Value to be searched: ");
scanf("%d",&x);
while((first<=last)&&(pos==-1)){
middle=(first+last)/2;
if(list[middle]==x)
pos=middle;
else
if(list[middle]<x)
first=middle+1;
else
last=middle-1;
}
if(pos>-1)
printf("\n The Position of the element is: %d ",pos);
else
printf("\n Search Unsuccessfull!!\n");
printf("\nWant to continue(y/n):");
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
return 0;
}Output of the program to search a element in the c program is as follows:
Binary Search in Python
Program to search a element using python is as follows:
def binary_search(arr, a, low, high):
if high >= low:
mid = low + (high - low)//2
# If found at mid, then return it
if arr[mid] == a:
return mid
# Search the left half
elif arr[mid] > a:
return binary_search(arr, a, low, mid-1)
# Search the right half
else:
return binary_search(arr, a, mid + 1, high)
else:
return -1
arr = input('Enter the list of numbers in ascending order ')
arr = arr.split();
arr = [int(x) for x in arr]
a = int(input('The number to search for: '))
index = binary_search(arr, a, 0, len(arr)-1)
if index != -1:
print("Element is present at index " + str(index))
else:
print("Not found")Output of the program to search a element in the c program is as follows:
Related Link: