Binary Search
Suppose there are billions(1*10^9) of numbers in an array. The array is sorted.
How would you approach to look if a number is present or not in that array?
Linear Search couldn’t be an option as the size of an array is too big.
An average c++ online ide would take 1*10^9/10^8 sec, i.e, 10 sec.
Note: The average c++ online ide can do approx 10^8 operations per sec.
But wait, we didn’t use sorted array information in our implementation of search. That is where Binary Search comes to rescue us by bringing down the complexity to log_2(n). It would take log_2(10^9)/10^8 sec, i.e, .3*10^{-6} sec.
We can see how drastically time complexity has reduced.
Let’s visualize Binary Search Algorithm with an example. Say we want to see if the number “9” is present in the array below.
If the Seach element is greater than the mid element it means we need to look rightwards of mid. Otherwise leftwards of mid.
Binary Search Algorithm Code
Let’s see Binary Search in c language.
int l=0; //left index
int r=n-1; // right index, n is the size of array.
int m; // mid element index
int k=9; // search element
while(l<=r)
{
m = (l+r)/2;
if(a[m] == k) {cout<<"element found\n"; break;}
else if(a[m] < k) l= m+1 ; // means k is present rightwards of m. so update l.
else r= m-1; // k is presnt leftwards of m. so update r.
}
Binary Search Time Complexity
Let’s say at the t iteration of Binary Search we found our element.
Notice that after every iteration size of an array is reduced by a factor of 2.
So, the length of the array after the t iteration is n/2^t.
Considering worst-case complexity, the size would have been reduced to 1.
so, 1 = n/2^t
2^t = n
Applying log base 2 on both sides
log_2(2^t) = log_2(n)
t = log_2(n)
i.e, in the worst case we found the element at log_2(n) step.
So the complexity is log_2(n)