Binary Search and Sorting for Coding Interviews

Binary search finds things in O(log n): a sorted list of a billion items takes about 30 steps. The idea is simple, but it's famous for off-by-one bugs, so it's worth learning one version well and using it every time.

Looking up a name in a phone book: open it in the middle, decide which half the name is in, and never look at the other half again.

The idea

In a sorted list, look at the middle item. If it's the target, you're done. If the target is bigger, it can only be in the right half; if smaller, only in the left half. Each step throws away half of what's left.

Binary search for 381 / 3

lowmidhigh

21 < 38, so 38 can only be to the right of mid.

python

1def find(items, target):

2    low, high = 0, len(items) - 1      # the target, if present, is in items[low..high]

if target is here, it's in items[low..high]

3    while low <= high:

stop when the range is empty

4        mid = (low + high) // 2

5        if items[mid] == target:

6            return mid

7        if items[mid] < target:

8            low = mid + 1                 # it's to the right of mid

mid is ruled out: + 1

9        else:

10            high = mid - 1                # it's to the left of mid

mid is ruled out: − 1

11    return -1

Keep a sentence in your head that's true on every loop, like the comment above: "if the target is here, it's between low and high." Every update must keep that sentence true and make the range smaller. That's how you avoid infinite loops and missed items.

Watch out
The classic bug: writing low = mid instead of low = mid + 1. When low and high are next to each other, that loops forever.

Variations to know

First or last position: when you find the target, don't stop. Record it and keep searching left (for the first) or right (for the last).
Insert position: when the loop ends, low is where the target would go to keep the list sorted. That's what Python's bisect.bisect_left returns.
Rotated sorted lists: one half around mid is always in order. Check whether the target falls in that half.

Binary search on the answer

Some problems don't have a sorted list at all, but have a yes/no question that flips once: "Can we finish with capacity c?" is no, no, no, then yes, yes, yes as c grows. Binary search over c to find the first "yes". The check is often a simple O(n) loop, giving O(n log range) overall.

Signs to look for: "minimum capacity", "smallest maximum", "least time such that...".

Can we ship with capacity c?

first yes

Amber is "no", green is "yes". The answer flips once, so binary search can find the first yes.

Sorting: what to know

You'll rarely write a sort in an interview, but you should know the costs:

Algorithm	Time	Extra space	Stable?	Notes
Merge sort	O(n log n) always	O(n)	Yes	Splits, sorts halves, merges
Quicksort	O(n log n) average, O(n²) worst	O(log n)	No	Fast in practice
Heapsort	O(n log n) always	O(1)	No	Uses a heap
Counting sort	O(n + k) for values 0..k	O(k)	Yes	Only for small integer ranges
Built-in sort (Python, modern JavaScript)	O(n log n)	O(n)	Yes	Timsort

Stable means items with equal keys keep their original order, which matters when you sort by one field and then another.

Common mistakes

while low < high with high = mid - 1, or mixing styles: pick one template and stick to it.
Forgetting that binary search needs sorted data (or a yes/no question that flips once).
In JavaScript, .sort() without a compare function sorts numbers as strings.

Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.