Binary Search

Sorting and Searching · 25 min

DSA · Searching

Throw away half the array, every time

Binary search finds a value in a sorted list of a million items in 20 reads. You will trace the low / mid / high window by hand, write the overflow-safe mid, and add the one-line tweak that returns the first match instead of any match.

Step the window through a 7-element array →
7 candidateswindow 0..6 · read index 3
→
3 candidateswindow 0..2 · read index 1
→
1 candidatewindow 2..2 · answer index 2

01 The idea

Halving beats scanning

You have a sorted list of a million roll numbers and you want to know whether 812345 is in it. Reading them one at a time can cost a million reads. Binary search reads the middle one instead. That single read tells you which half the answer cannot be in, and you delete that half — half a million candidates gone for the price of one comparison.

Repeat, and the candidate count goes 1,000,000 → 500,000 → 250,000 and onward. After 19 reads at most one candidate is left, and the 20th read either finds the target sitting there or empties the window for good — 20 reads, worst case, for a million values. The only thing you pay for that is the precondition: the list must already be sorted, because the whole argument rests on "everything to the left of a bigger value is also bigger".

Look at the middle of what is left. If it is the target, you are done. If it is too small, throw away the left half; if it is too big, throw away the right half. Repeat on what survives.
Sorted orderEvery value is less than or equal to the one after it. Binary search never checks this. On unsorted input it returns a wrong index confidently instead of failing.
Search windowThe stretch low..high that could still hold the target. Everything outside it has been ruled out and is never read again.
MidThe middle index of the window, low + (high − low) / 2, rounded down. With two or more elements it is never equal to high, which is what keeps the window shrinking.

02 Worked example

Finding the first 4 in 1 3 4 4 4 7 9

Seven values, already sorted, with the target repeated three times. The window starts as the whole array — low = 0, high = 6 — and you are hunting for 4. The first three rows are the three passes of the loop; the fourth is the exit check that finds the window empty, and the fifth is the answer. On a loop row, read the label for the current window, the rose box for the element actually read, and the note for what happened next.

index0123456
win 0..61344479mid 3 · 4 = 4 · save 3, high ← 2
win 0..21344479mid 1 · 3 < 4 · low ← 2
win 2..21344479mid 2 · 4 = 4 · save 2, high ← 1
win 2..11344479low > high · window empty · stop
result1344479first 4 is at index 2 · 3 reads
Plain binary search would have stopped on the very first row. a[3] is 4, so it returns index 3 and never looks left. That is a correct match. It is not the first match.

Three reads, and the candidate count went 7 → 3 → 1 → 0. Notice what did the real work: the first read found a 4 immediately, but instead of returning, the trace wrote the index down and shrank the window to the left. Record, then keep going — that single decision is the whole difference between the two versions of the code below.

03 The code

Plain search, then the leftmost tweak

Both versions carry the same window low..high with both ends inclusive, compute mid the same way, and both stop when low passes high. Four lines change, and only one of them is a real idea: line 4 records the match instead of returning it. Line 1 adds the ans variable to record into, line 5 becomes an else if because line 4 no longer exits the loop, and line 7 returns ans rather than a bare −1.

Plain — returns any match

low = 0;  high = n − 1while low <= high:    mid = low + (high − low) / 2   # floor    if a[mid] == target:  return mid    if a[mid] <  target:  low  = mid + 1    else:                 high = mid − 1return −1   # window empty

First occurrence — returns the leftmost

low = 0;  high = n − 1;  ans = −1while low <= high:    mid = low + (high − low) / 2    if a[mid] == target: ans = mid; high = mid − 1    else if a[mid] < target: low  = mid + 1    else:                    high = mid − 1return ans  # smallest matching index

Why low + (high − low) / 2 and not (low + high) / 2? They are the same number in mathematics, not in fixed-width integers. If low and high are both near the 32-bit limit, the sum wraps around to a negative number and mid indexes out of bounds. The subtraction form never builds a value larger than high, so it cannot wrap. This exact bug sat inside the Java standard library binary search for nine years.

Why record instead of return? Returning on the first match is what made the trace stop at index 3. Saving mid into ans and then setting high = mid − 1 says "I have a valid answer, now prove there is an earlier one". Every later match overwrites ans with a smaller index, so when the window finally empties, ans holds the leftmost one.

Why high = mid − 1 and never high = mid? Every branch has to move a boundary past mid, so the window loses at least the middle element each pass. In a two-element window mid equals low, so high = mid would leave the window unchanged and the loop would spin forever. That same guarantee is the termination proof: a window that always shrinks must reach empty.

05 Cheat sheet

Numbers worth memorising

CaseCostWhat causes it
Best case, plain searchO(1)The very first mid is the target. On 1 3 4 4 4 7 9 that happens: a[3] is 4, so plain search finishes in 1 read.
Average and worst caseO(log n)The window halves each pass. At most ⌊log₂ n⌋ + 1 reads before it empties.
First-occurrence variantO(log n)Never stops early — it runs the window down to empty every time, so there is no O(1) best case. On n = 7 that is always 3 reads; on n = 1,000,000 it is 19 or 20.
Space, iterativeO(1)Three integers: low, high, mid.
Space, recursiveO(log n)One stack frame per halving, unless the compiler eliminates the tail call.
Sorting first, if the input is unsortedO(n log n)The sort dominates completely. For a single lookup an O(n) scan is cheaper.
Sorted, alwaysBinary search never verifies the order. On unsorted input it returns a wrong index confidently — no crash, no error, just a wrong answer.
Random access, alwaysReaching mid must cost O(1). On a linked list each read costs O(n) hops, so the search degrades to O(n log n) — worse than a plain scan.
⌊log₂ n⌋ + 1The read budget. 7 → 3 reads, 1,000 → 10, 1,000,000 → 20, 1,000,000,000 → 30.

06 Where & why

Sorted data, or a boundary question

Binary search is not the fastest lookup you can build — a hash table answers an exact-key question in O(1) and does not care about order at all. What binary search gives you is the class of answers a hash table cannot produce: the first value that is at least x, the position a new value belongs in, the two edges of a repeated run.

Reach for it when…

The order is already paid forA database index, a sorted log file, a leaderboard, the output of a merge. You get O(log n) without ever spending the O(n log n).
The question is a boundary, not a keyFirst value at least x, the insertion point, the first and last index of a run. A hash table cannot answer any of these.
Many lookups, one sortq linear scans cost q·n; sorting once and then searching costs n log n + q log n. Solve for q and the break-even sits at roughly log n queries — a few dozen on a million-element array, not thousands.
The answer space is monotoneSmallest capacity that works, minimum number of days, largest feasible size. If a yes/no test flips from false to true exactly once, you can binary-search the answer itself.

Use something else when…

SituationBetter choiceWhy
You only ever look up by exact key, and order never mattersHash table / dictionaryO(1) average beats O(log n), and you skip the sorting cost entirely.
The data is unsorted and you will search it onceLinear searchO(n) beats O(n log n) of sorting plus O(log n) of searching.
The elements sit in a linked listLinear scan, or copy into an arrayReaching mid costs O(n) hops, so every read is O(n) and the log n saving evaporates.
Values are inserted and deleted constantlyBalanced BST, skip list, std::setThey keep order under insertion in O(log n); a sorted array costs O(n) to shift on every insert.
In real code you will call bisect_left, lower_bound, or Arrays.binarySearch, and they already handle the safe mid and the leftmost match. Interviews still make you write it, because the low / mid / high invariant is what people get wrong under pressure — and that same invariant is what lets you binary-search an answer space with no array in sight.

07 Interview questions

What interviewers actually ask

Eleven questions in the order an interview escalates: what it is, how fast, why that fast, and then the duplicate-handling follow-up that decides the round.

What is binary search?
It finds a value in a sorted array by repeatedly halving the range it still has to look at. You compare the middle element to the target: too small and you drop the left half, too big and you drop the right half. Each read throws away half the remaining candidates, so n elements need about log₂ n reads instead of n.
What has to be true about the array before you can run it?
It must be sorted on the same key you are searching by, and you must be able to reach any index in O(1) time — those two, and nothing else. Binary search never verifies the order — on unsorted input it returns a confident wrong index rather than an error. On a linked list every read costs O(n) hops, so the log n read count buys you nothing.
Why is it O(log n) and not O(n)?
The candidate count goes n, then n/2, then n/4, and so on, so the number of halvings before one candidate is left is log₂ n — one more empties the window, giving the ⌊log₂ n⌋ + 1 bound. The work inside one pass is a single comparison and a single assignment, so the total is O(log n).
Worst case, how many comparisons for 7 elements? For a million?
The bound is ⌊log₂ n⌋ + 1. For 7 that is 3 — the window goes 7 → 3 → 1 → 0, exactly what the trace showed. For a million it is 20, because 2²⁰ is 1,048,576 while 2¹⁹ is only 524,288. A linear scan would need up to a million reads; that gap is the entire point of the algorithm.
What is the space complexity?
O(1) for the iterative version — it holds only low, high and mid. The recursive version is O(log n) because each halving leaves a stack frame behind. That recursion is tail recursion, so a compiler which eliminates tail calls gets you back to O(1), but do not assume Python or Java does it.
Why write mid = low + (high − low) / 2 instead of (low + high) / 2?
They are equal in mathematics but not in fixed-width integers. If low and high are both large, low + high overflows and mid comes out negative, which then indexes out of bounds. The subtraction form never builds a value bigger than high. This exact bug lived in the Java standard library binary search for nine years before anyone hit it.
How do you know the loop always terminates?
mid always lies inside low..high, and every branch moves a boundary past it — either low = mid + 1 or high = mid − 1. So the window loses at least one element per pass and can never repeat a state. It ends either by returning or when low passes high.
On 1 3 4 4 4 7 9, searching for 4 returns index 3. How do you get index 2 instead?
Stop returning on a match. Save mid into an answer variable, set high = mid − 1, and keep looping. Every later match overwrites the answer with a smaller index, so when the window empties the answer holds the leftmost one. The price is that you can never stop early: the window always runs down to empty, so you lose the O(1) best case and pay Θ(log n) every time. On this array that is 3 reads instead of 1.
In that tweak, why high = mid − 1 and not high = mid?
With while low <= high, a two-element window has mid == low, so high = mid leaves the window unchanged and the loop never ends. mid − 1 guarantees it shrinks every pass. The half-open template while low < high with high = mid is a different, also-correct pattern — pick one and never mix the two.
How would you count how many times a value appears, in O(log n)?
Run the first-occurrence search, then run the mirror of it that records a match and sets low = mid + 1 to get the last occurrence. The count is last − first + 1, or 0 if the first search returned −1. Two O(log n) passes is still O(log n). Finding one copy and walking outwards is O(n) when the array is a single repeated value.
Binary search or a hash table — when would you actually pick binary search?
Pick binary search when the data is already ordered, or when the question is about a boundary rather than a key — the first value at least x, the insertion point, the edges of a repeated run. A hash table answers none of those, and it cannot be run over an answer space, which is where binary search shows up in most interview problems. For plain exact-key lookup the hash table wins: O(1) average and no sorting cost.

08 Practice problems

Six problems, in order of bite

Every one is solvable with only what is above: the inclusive window, the overflow-safe mid, and the record-and-keep-going tweak.

Plain lookup

Easy
Given a sorted array and a target, return any index holding the target, or −1 if it is absent.
Follow-up
The array may hold up to two billion elements, so (low + high) / 2 overflows a 32-bit integer. The safe mid is not optional here.
Show the hint
Keep the window inclusive at both ends, and check that every branch moves a boundary past mid.

Last occurrence

Easy
Return the index of the last occurrence of the target in a sorted array, or −1 if it is absent.
Follow-up
It is the mirror of the lesson tweak, and getting the direction wrong hands you the first occurrence instead — a bug that passes every test which happens to have no duplicates.
Show the hint
You still record the match. Ask which boundary has to move to prove there is a later copy, and move that one instead.

Insertion point

Medium
Return the index where the target should be inserted to keep the array sorted; if it is already present, return the leftmost such index.
Follow-up
There is no found case at all. The loop must always run until the window is empty, and the answer is whatever low holds at that moment.
Show the hint
Never return from inside the loop; convince yourself that low ends up on the first index whose value is at least the target.

Count a value

Medium
Return how many times the target appears in a sorted array, in O(log n) time.
Follow-up
Finding one copy and walking outwards is O(n) when the whole array is one repeated value, so you need two independent searches rather than one search plus a scan.
Show the hint
You already have the leftmost index from the lesson and the rightmost from problem 2. Work out what arithmetic turns those two indices into a count, and what to return when the first search reports −1.

Integer square root

Medium
Return the floor of the square root of a non-negative integer x, without calling any square-root function.
Follow-up
There is no array. You binary-search the answer range 0..x, and the test mid × mid <= x supplies the sorted structure — true for a prefix of the range, false after it.
Show the hint
Same record-and-keep-going shape: save mid whenever mid × mid <= x, then search the right half for a bigger one.

Smallest shipping capacity

Hard
Given package weights in a fixed order and a number of days D, return the smallest ship capacity that lets you ship every package, in order, within D days.
Follow-up
The search space is not the array — it is the capacity range from the heaviest package up to the total weight, and the property "capacity C finishes within D days" is false for a while and then true forever. That single flip is the sortedness binary search needs.
Show the hint
Write feasible(C) as one greedy left-to-right pass that counts days, then run the first-occurrence search over C to find the leftmost capacity where it is true.