Classic binary search

35 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A sorted list: −1, 0, 3, 5, 9, 12. Is 9 in it, and at which position? Reading left to right you check −1, 0, 3, 5, then 9: five looks. If the list had a million numbers and 9 sat near the end, that would be a million looks.

But you would never search a dictionary that way. You open it near the middle, see which half the word belongs in, and ignore the other half completely. The list being sorted is what makes this legal: if the middle number is 5 and you want 9, everything left of 5 is at most 5, so 9 cannot be there.

Build the structure, one piece at a time

There is no new container here. The structure is the pair of boundaries, lo and hi, which mark the part of the list where the target might still be.

Piece 1: the range. Start with lo = 0 and hi = 5, the whole list (positions 0 to 5).

Piece 2: the middle. Compute mid = (lo + hi) ÷ 2, rounding down, and look at that one number.

Piece 3: throw away half. If the middle number equals the target, done. If it is smaller than the target, the target can only be to the right: set lo = mid + 1. If it is bigger, set hi = mid − 1. Repeat until lo passes hi, which means the target is not there.

Two looks instead of five. (The video runs the same search over an 8-slot layout so it takes three halvings; the mechanism is identical.) Searching for 4, which is absent, goes: mid 2 (3 < 4, lo = 3), mid 4 (9 > 4, hi = 3), mid 3 (5 > 4, hi = 2), and now lo = 3 > hi = 2, so 4 is not in the list. Notice lo ended at 3, exactly where 4 would be inserted to keep the list sorted.

Why it is correct

The invariant: if the target is in the list, its position is between lo and hi inclusive.

At the start the range is the whole list, so it holds. When nums[mid] < target, every position ≤ mid holds a value ≤ nums[mid] < target, because the list is sorted, so none of them is the target; moving lo to mid + 1 drops only positions that cannot hold it. The mirror argument covers nums[mid] > target. So the invariant survives every step, and when lo > hi the range is empty, which means the target is absent.

Two details catch people. Use lo ≤ hi as the loop condition, so a range of one element is still checked. And write mid = lo + (hi − lo) ÷ 2 in languages with fixed-size integers, so lo + hi cannot overflow.

Why it is fast

Every step cuts the range to at most half its size. Starting from n positions, after k steps at most n / 2^k remain. The search ends once that is below 1.

n / 2^k < 1  when  k > log₂ n, so about log₂ n looks

For a million numbers, log₂(1 000 000) is about 20. Twenty looks instead of a million. Doubling the list adds one look.

How to recognise it in an interview

The word "sorted" is the big cue, plus "find", "first position", "insert position", or a 2-D matrix whose rows and columns are sorted (treat it as one long sorted list of m × n cells). Say: "The input is sorted, so I can halve the search range each step; that is O(log n)."

Binary Search is the example above. Search Insert Position returns lo when the loop ends, which is where the target belongs. Search a 2D Matrix maps index i to row i ÷ cols and column i mod cols and runs the same search. Sqrt(x) searches the integers 0 to x for the largest value whose square is at most x.

02The idea in one line

Halve the sorted range by comparing with the middle.

Reach for it when: Sorted array lookups, first/last position, insert position, 2D matrix search.

Cost: O(log n) time.

03The walk-through, step by step

The video works one example: Binary Search for 9 in [-1,0,3,5,9,12]. These are its captions in order, so you can follow without the video or check a step you missed.

1. The target, if present, lives inside [lo, hi]
2. mid = (0 + 7) // 2 = 3, nums[mid] = 5
3. 5 < 9: drop the left half, lo = 4
4. mid = (4 + 7) // 2 = 5, nums[mid] = 12
5. 12 > 9: drop the right half, hi = 4
6. mid = (4 + 4) // 2 = 4, nums[mid] = 9
7. nums[4] = 9: found at index 4
8. Each step halves the range: O(log n) comparisons

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search: First true (predicate boundary), Binary search on the answer, Rotated / mountain search, Partition two sorted arrays.