This is a short note on using binary search, in continuance of my series on Algorithms.
Suppose we have to find whether a particular element exists in the sorted list of N numbers or not.
Let “arr” be the array which contains the N elements and the element to be searched is “key”.
Then, the time complexity using brute force will be O(N).
CODE-
[cpp]
for(i=0;i<N;i++)
{
if(arr[i]==key)
{
printf("Element is found\n");break;
}
}
[/cpp]
But,using binary search,the time complexity will be O(log(N)).A binary search halves the number of items to be checked each time and thus has logarithmic complexity.
ALGORITHM-
In this algorithm,the key is compared with the middle element of the array.
Cases:
1.If the middle element is equal to the key,then the search is completed.
2.If the key is less than the middle element,then the algorithm is repeated on the sub-array to the left of the middle element.
3.If the key is greater than the middle element,then the algorithm is repeated on the sub-array to the right of the middle element.
4.If the remaining array to be searched is empty,then the key cannot be found in the array and the search is completed.
CODE-
Recursive solution-
[cpp]
int binarysearch(int arr[],int key,int beg,int last)
{
// beg and last indicate the starting and ending indices of the subarray.
// Initially,beg has the value 0 and last has the value n-1.</em>
if(beg >last) return 0; // key not found</em>
else
{
int mid=(beg+last)/2; // finding the middle element</em>
if(key==arr[mid])return 1; // key found</em>
else if(key < arr[mid]) return binarysearch(arr,key,beg,mid-1);
else
return binarysearch(arr,key,mid+1,last);
}
}
[/cpp]
NOTE- Binary Search is used only when the given list is sorted.If the list is unordered,brute force is better as sorting will have a complexity of O(N*log(N)).
