Finding the exact spot where "no" turns into "yes"

Tier 1Free

Elman HuseynovUpdated 2026-10-22

Level

Where it runs

1. The problem

A bug got into your app. Version 40 works. Version 90 is broken. Somewhere in between, one change (one commit) broke it. From that commit on, every build fails. You want the first bad version.

Checking one version is slow: you build it and run all the tests. There are 50 versions between 40 and 90. Checking them one by one means 50 test runs. That is hours of waiting.

The results have an order, though. First come builds that pass, then builds that fail, all the way to the end. Once a build breaks, it stays broken in every later version.

That order lets you find the switch point in about 6 checks instead of 50. You find it with the same halving as in the last lesson. There you looked for one exact value. Here you look for the place where "works" changes to "broken".

2. In plain words

Take 6 positions, numbered 0 to 5. The check answers "no" on positions 0, 1 and 2 and "yes" on positions 3, 4 and 5. You don't know that in advance, and you want the first "yes".

Check the middle position, number 3. The answer is "yes". So the first "yes" is at position 3 or earlier, and you never need to check positions 4 and 5. Check position 1: "no". So everything before it is "no" too, and the first "yes" is further right. Position 2 is left: "no". So the first "yes" is at position 3.

Look at the first step to see how this differs from ordinary binary search. Position 3 said "yes", and the search went on. You didn't yet know that position 2 would say "no", so you kept looking to the left. You want the very first "yes", and at that moment you could not tell whether position 3 was it.

3. The idea

You have a yes/no check. Here it is isFailing(version). The check is monotonic: once it answers true, it answers true at every later position too. So the answers look like false, false, ..., true, true, true. You want the first true.

Work with a range from lo to hi. At the start lo = 0 and hi = n. Keep one rule true the whole time. At every position left of lo the check gives false. At position hi and everywhere right of it the check gives true. Position n is not in the list: it sits right after the last one. Starting with hi = n leaves room for the answer "there is no true at all".

Repeat while lo < hi. Look at the middle. If it is true, the first true is at the middle or to its left. So bring hi down to mid. Use mid, not mid - 1: mid itself might be the answer. If it is false, the first true is strictly to the right. So move lo up to mid + 1. When lo and hi meet, that is the first index with true. If there was no true at all, they meet at n.

The main difference from the last lesson: when you find a true, you don't stop. Ordinary binary search returns as soon as it finds a match. This search remembers the place in hi and keeps looking to the left. That is why it finds the very first position, even when many positions match.

Trace it with n = 6 and the check "index ≥ 3":

Start: lo = 0, hi = 6. The middle is 3, which gives true, so hi = 3.
Now lo = 0, hi = 3. The middle is 1, which gives false, so lo = 2.
Now lo = 2, hi = 3. The middle is 2, which gives false, so lo = 3.
Now lo = 3, hi = 3. They have met. Return 3.

4. What it costs

Time: O(log n) calls to the check, because the range halves at every step. Memory: O(1), just two indices.

Here the number of calls to the check counts more than usual. One call can mean a whole build, or a network request that takes several seconds. 6 calls instead of 50 means a short coffee break instead of waiting until lunch.

6. Where this shows up

git bisect narrows a range of commits (code changes) to the first bad one in exactly this way. Rollout thresholds for feature flags (switches that turn a new feature on for part of the users). The functions lower_bound and upper_bound in standard libraries; subtracting one from the other gives how many times a value appears. Finding the first log entry after a given moment. Rate and quota tables, where you look for the first tier a value falls into.

Recognise it

Binary search (array)

Say these words and it is this pattern

sorted array
find a target / first or last occurrence
n up to 1e6+ and O(log n) expected
find the boundary where a condition flips
search a rotated-but-mostly-sorted array (with a twist)

Looks similar, isn't

Linear search
A scan reads every element but assumes no order. Binary search demands order and reads log n.
Binary search on a rotated array
A rotation breaks the single sorted run. The check must find the sorted half first.
Binary search on the answer
There the range is the set of possible answers, not an array. The test is a function you write.
Binary search tree
A tree halves the same way but through pointers. It also allows inserts, which an array does not.
Two pointers (opposite ends)
Both ends move there, and the pair being tested changes. Here only one bound moves per step.

n up to 1e9 is fine, because log2 of 1e9 is about 30. Time is O(log n), space is O(1).

On LeetCode

Problems that ask for the first place where an answer flips from no to yes, such as the first bad version, an insert position, or the first and last copy of a value. Keep hi on a yes and move lo past a no.

278.First Bad Version (opens in a new tab)Easy
The lesson's git bisect story, with isBadVersion as pred.
35.Search Insert Position (opens in a new tab)Easy
The first index whose value is at least target, and n when there is none.
744.Find Smallest Letter Greater Than Target (opens in a new tab)Easy
The first letter strictly greater than target, wrapping to the first letter when there is none.
34.Find First and Last Position of Element in Sorted Array (opens in a new tab)Medium
Two boundary searches, one for the first index at least target and one for the first index past it.

Your task (Tier 1)

Write the function firstTrue(n, pred).

pred(i) is a yes/no check. You can call it on any position i from 0 to n - 1. For a while it answers "no", then "yes", and it never goes back to "no". Find the first position where it answers "yes". If it never says "yes", return n.

Input: n, the number of positions (from 0 to n - 1), and pred, a function that takes a position and returns true or false. Example: n = 6 and a check that gives true when i >= 3.
Return: the smallest position where pred gives true, or n if it never gives true.

Steps:

Set lo = 0 and hi = n.
While lo < hi, take the middle position mid. If pred(mid) gives true, the answer is at mid or to its left, so set hi = mid. If it gives false, the answer is to the right, so set lo = mid + 1.
When lo and hi meet, return lo.

The tests give the check's answers as a list flags: position i answers flags[i], and n is the length of the list.

Done when all tests pass:

[false, false, false, true, true, true] -> 3 (true starts in the middle)
[false, false, false, false, true] -> 4 (true only at the last position)
[true, true, true] -> 0 (true from the very start)
[false, false, false] -> 3 (never true, so return n, which is 3)
[false, true, true, true, true] -> 1 (the list [1, 2, 2, 2, 5] checked with nums[i] >= 2)
[true] -> 0 and [false] -> 1 (n = 1)
[] -> 0 (n = 0, no positions at all)

Practice

firstTrue

firstTrue(n, pred) -> the first index where pred is true, or n

// firstTrueFlags is given: it passes a list of flags (all false first, then
// all true) to your firstTrue. Write firstTrue below. The task is described in the box above the editor.

export function firstTrue(n, pred) {
  // Your code here. The task is described in the box above the editor.
}

export function firstTrueFlags(flags) {
  return firstTrue(flags.length, (i) => flags[i]);
}

Running as a guest

The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.

Create a free account Log in

Hint ladder

Stuck? Reveal one rung at a time, but try it yourself first.

PreviousFinding one item in a sorted list by halving NextBinary search in a rotated sorted array