Binary Search Algorithm


Binary Search Algorithm

For any sorted array of n element, to find the position of any value m in that array is the work of Binary Search Algorithm. 

The time complexity of this algorithm is O(log n).

Binary Search Algorithm compares the searched value with the middle element value of the array. If they match, then the searched

is found and the position of that value is returned. Otherwise, if the searched value is less than the middle element's value, then the algorithm repeats its action on the sub-array to the lest of the middle element or, if the search value is greater , then the value next to the middle element is assigned as the highest value and the same process is repeats for the sub-array until the search value

matches the middle value.


Program of Binary Search Algorithm :


#include<iostream>
using namespace std;
int main()
{
int arr[10];
int i, j, num, temp, keynum;
int low, mid, high;
cout<<"Enter the no. of values"<<endl;
cin>>num;
cout<<"Enter the elements in the array one by one"<<endl;
for(i=0; i<num; i++)
{
cin>>arr[i];
}
for(i=0; i<num; i++)
{
for(j=0; j<(num-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
cout<<"sorted array is:"<<endl;
for(i=0; i<num; i++)
{
cout<<arr[i]<<endl;
}
cout<<"Enter the element to be searched"<<endl;
cin>>keynum;
low=1;
high=num;
do
{
mid=(low+high)/2;
if(keynum<arr[mid])
high=mid-1;
else if(keynum>arr[mid])
low=mid+1;
}while(keynum!=arr[mid]&&low<=high);
if(keynum==arr[mid])
{
cout<<"Search successful"<<endl;
cout<<"number located at position"<<mid+1<<endl;
}
else
{
cout<<"search failed, number not found"<<endl;
}
return 0;
}


Output:

Binary Search Algorithm

Binary search

Custom Search

%d bloggers like this: