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)).
Sreekumar (KJ) has been a hobby programmer from school days. Codemarvels is his personal blog from the year 2010, where he writes about technology, philosophy, society and a bit about physics.
He now runs a conversational AI company – DheeYantra – focusing his efforts to help businesses improve operational efficiency using digital employees powered by AI.