Suppose, is a of integers that are sorted in nondecreasing order. We need to determine whether an element is present in the or not. There are elements in the . numbers list/array x list n list Linear search Before using let’s check how linear search will perform in this problem. binary search Let’s, n = 10⁶ ( here, is a list of 10⁶ integers).If x is present at the first position of the then we will get our expected result at the first iteration. This will work in time. Pretty fast! NO? numbers list O(1) But if x is present at 10⁶th position(or not present in the list) then it will take time to calculate the result and if we search for n times then time complexity will be , pretty slow, NO? O(n) O(n²) So we can say that, at worst case linear search will work in time complexity (for n number of elements and n number of searches). O(n²) Here will do the trick! binary search Binary Search Binary search works using 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? divide-and-conquer Every time divides the original search space into two equal sized search space (depending of implementation logic it may change). binary search 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 will work also? x == numbers[high] 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 (not , high is one more than the highest possible index). If we used then it would work instead of some corner cases. If our expected element is the last element and then will never be able to point the last element. high=n n-1 high=n-1 high=n-1 low For example, call the optimized function using the following data (once using high=n-1 and then using high=n), this will clear the scenario. binary_search numbers = [1, 2, 3, 4, 5] n = 5 x = 5 : Instead of we can write: Additional Note return x == numbers[low] Comparison to linear search : At worst case, for n number of elements and n number of searches linear search will have time complexity.For sorted numbers, binary search will have complexity [for n number of searches].If the numbers are not previously sorted then we can use or algorithms (both of them have time complexity) and then apply binary search. O(n²) O(nlogn) quick sort merge sort O(nlogn) 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 will perform better than ! O(nlogn) O(nlogn) 2*O(nlogn) O(nlogn) binary search linear search You can also read : Understanding Python decorators Functions as first class object in Python Playing with inheritance in Python Closure in Python and Javascript Developing our first PWA using React React navigation cheatsheet Min priority_queue in C++ Naming your variables!
