Suppose, numbers is a list/array of integers that are sorted in nondecreasing order. We need to determine whether an element x is present in the list or not. There are n elements in the list .
Linear search
Before using binary search let’s check how linear search will perform in this problem.
Let’s, n = 10⁶ ( here,numbers is a list of 10⁶ integers).If x is present at the first position of the list then we will get our expected result at the first iteration. This will work in O(1) time. Pretty fast! NO?
But if x is present at 10⁶th position(or not present in the list) then it will take O(n) time to calculate the result and if we search for n times then time complexity will be O(n²), pretty slow, NO?
So we can say that, at worst case linear search will work in O(n²) time complexity (for n number of elements and n number of searches).
Here binary search will do the trick!
Binary Search
Binary search works using divide-and-conquer approach. At every iteration it breaks the original problem into sub-problems and solution of sub-problems will be solution of original problem. Interesting, YES?
Every time binary search divides the original search space into two equal sized search space (depending of implementation logic it may change).
With the help of knowledge of logarithm we can guess that binary search will take at most log2(10⁶) = 19.93 ~20 iterations for this problem (where linear search may take at most 10⁶ iterations!). Notice better the performance!
Iterative approach
Following code snippets are iterative approach of binary search :
Python code :
Javascript code :
Recursive approach
Following code snippets are recursive approach of binary search :
NOTE : For recursive approach conditions of breaking the recursion should be appeared first, otherwise you may fall in infinite loop!
Python code :
- * Can you guess why return
x == numbers[high]will work also?
Javascript code :
More optimization (variation of binary search) :
Find the differences between previous codes the the following iterative ones :
Python code :
Javascript code :
Notice, we’ve less comparisons here (can you find which ones?). This will improve performance significantly.
Now, look at line 8, we’ve used high=n (not n-1, high is one more than the highest possible index). If we used high=n-1 then it would work instead of some corner cases. If our expected element is the last element and high=n-1 then low will never be able to point the last element.
For example, call the optimized binary_search function using the following data (once using high=n-1 and then using high=n), this will clear the scenario.numbers = [1, 2, 3, 4, 5] n = 5 x = 5
Additional Note : Instead of return x == numbers[low] we can write:
Comparison to linear search :
At worst case, for n number of elements and n number of searches linear search will have O(n²) time complexity.For sorted numbers, binary search will have O(nlogn) complexity [for n number of searches].If the numbers are not previously sorted then we can use quick sort or merge sort algorithms (both of them have O(nlogn) time complexity) and then apply binary search.
In this case,Total worst case time complexity = Worst case time complexity of sorting (let merge sort) + worst case time complexity of binary search = O(nlogn)+O(nlogn) = 2*O(nlogn)~O(nlogn)We can decide that, if the numbers are not sorted, still binary search will perform better than linear search!