Binary search
Python Binary Search Interview Questions
Binary search halves a sorted range over and over until it finds what it is looking for. It is short to write and easy to get subtly wrong, which is exactly why it keeps appearing in interviews.
What binary search questions ask you to do
Across the questions here, these are the shapes that come up:
- Find a value, or report that it is not there
- Find the position where a value would be inserted
- Find the first or last of a repeated value
- Search a sorted sequence that has been rotated
Common mistakes with binary search
The loop condition and the way the boundaries move have to agree with each other. Mixing the two common forms either loops forever or misses the last item, and both failures only appear on particular inputs, so a quick test will not catch them.
