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
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).
binary search will do the trick!
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?
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!
Following code snippets are iterative approach of binary search :
Python code :
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?
More optimization (variation of binary search) :
Find the differences between previous codes the the following iterative ones :
Python 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
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
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
We can decide that, if the numbers are not sorted, still
binary search will perform better than