First true (predicate boundary)

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

Eight versions of a program, numbered 1 to 8. Some version introduced a bug, and every version after it is also bad. You can call isBad(v), which is slow (imagine it runs a full test suite). Find the first bad version. Here the first bad one is 5, so the answers look like: good, good, good, good, bad, bad, bad, bad.

By hand you call isBad(1), isBad(2), … until the first bad answer: 5 calls here, up to n calls in general. With ten thousand versions that could be ten thousand test-suite runs.

Look at the shape of the answers: a run of falses then a run of trues, never switching back. Checking version 4 and seeing "good" tells you versions 1 to 3 are good too, without calling them. Checking version 6 and seeing "bad" tells you 7 and 8 are bad. One call eliminates a whole side.

Build the structure, one piece at a time

Again the structure is two boundaries, but with a different meaning from the classic search: we are not looking for a particular value, we are looking for the place where false turns into true.

Piece 1: the range of candidates. lo = 1, hi = 8. The first bad version is somewhere in [lo, hi].

Piece 2: test the middle. mid = (lo + hi) ÷ 2 = 4. isBad(4) is false.

Piece 3: move the correct boundary. If the middle is good, the first bad one is strictly after it: lo = mid + 1. If the middle is bad, the first bad one is mid or earlier: hi = mid. Note that hi = mid, not mid − 1, because mid itself could be the answer. Stop when lo equals hi.

Three calls instead of five, and for ten thousand versions about fourteen instead of ten thousand.

Why it is correct

Call the yes/no test a predicate. It is monotone: once it is true it stays true. The invariant is: isBad(lo − 1) is false (or lo is the first version), and isBad(hi) is true (or hi is past the end). So the first true lies in [lo, hi].

When isBad(mid) is false, monotonicity says every version up to mid is also false, so setting lo = mid + 1 keeps "isBad(lo − 1) is false" true. When isBad(mid) is true, setting hi = mid keeps "isBad(hi) is true" true. The range shrinks every step because mid < hi whenever lo < hi, so lo = mid + 1 and hi = mid both move. When lo = hi the two facts combine: lo − 1 is false and lo is true, so lo is the first true.

This is the same binary search as the classic one, but phrased as "find the boundary of a monotone predicate". Searching for a value x in a sorted list is the special case where the predicate is nums[i] ≥ x, and the boundary is the lower bound of x.

Why it is fast

Each call halves the number of candidate versions.

calls ≤ ⌈log₂ n⌉, so 10 000 versions need at most 14 calls

When the test is expensive, as a test suite or a network request is, this is the difference between a day and a minute.

How to recognise it in an interview

The cues are "first version that", "smallest index such that", "minimum x that satisfies", "leftmost or rightmost occurrence", or any yes/no condition that is false for a while and then true for good. Say: "The condition is monotone, so I binary search for the boundary, keeping hi on a known true and lo just past a known false."

First Bad Version is the example above. Find First and Last Position of Element in Sorted Array runs the boundary search twice, once with nums[i] ≥ target and once with nums[i] > target. Search Insert Position is the single boundary nums[i] ≥ target.

02The idea in one line

A monotone false…true predicate: find the first index where it flips.

Reach for it when: First bad version, lower/upper bound, leftmost insertion, 'minimum x such that'.

Cost: O(log n) evaluations.

03The walk-through, step by step

The video works one example: First Bad Version with n=8, first bad = 5. These are its captions in order, so you can follow without the video or check a step you missed.

1. A monotone predicate: find the first index where it turns true
2. mid = 4: isBad(4) = false
3. Good: the first bad is after 4, lo = 5
4. mid = 6: isBad(6) = true
5. Bad: the first bad is 6 or earlier, hi = 6
6. mid = 5: isBad(5) = true
7. Bad: the first bad is 5 or earlier, hi = 5
8. lo == hi == 5: the first bad version is 5
9. Keep lo on 'maybe', hi on 'definitely true': O(log n) calls

04Asked at Google

8 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: Classic binary search, Binary search on the answer, Rotated / mountain search, Partition two sorted arrays.