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

The key conditions to perform a binary search is the following:

• a minimum (can be index, value, row, depends on what we want to search)

• a maximum

• a validator to check the midpoint so we can determine which half to keep

Type of Questions

• Array problems (binary search on index)

  • Binary search (find target) on array

  • Decrease and conquer on array (pick half)

• Grid problems

  • Use a condition to eliminate half of the grid each turn

• Number problems (binary search on answers)

  • Binary search on the number line