Binary Search

Intro

You have a phone book. Find Mike Smith. You can go through page by page from the beginning. You are guaranteed to find Mike Smith by this algorithm. But it's very naive. What if we start from the middle? Since the phone book is sorted, we can rip the phone book in half and throw away the part that does not contain Mike Smith. We are fundamentally left with the same problem, but it's only half the size. The powerful part of this idea is that a 1000 page phone book takes 10 tears and a 4 billion page phone book only takes 32 tears.

Algorithm

1. Set L to 0 and R to n − 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
4. If Am < T, set L to m + 1 and go to step 2.
5. If Am > T, set R to m – 1 and go to step 2.
6. Now Am = T, the search is done; return m.

The algorithm is trivial but the underlying idea "decrease and conquer" - pick half of the original problem - is fundamental. The algorithm is intuitively recursive. Since we only have one subproblem after each "divide", we can convert the recursion to a while loop to save some space on the call stack.

Time Complexity

T(n) = T(n/2) + 1 we can pick half of the original problem with O(1) work. This recurrence guarantees us O(logn) worst case runtime. If we can come up with an O(n) brute force solution and the interviewer asks can you do better, binary search is probably the right approach.

Summary

• Array problems (binary search on index)
  • Binary search (find target) on array
  • Decrease and conquer on array (pick half)
• Number problems (binary search on answers)
  • Binary search on the number line