15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Binary search on the answer searches a range of possible values instead of an array. You write a yes-or-no test P(x) that is false up to some value and true after it, then halve the range to find the first true value. It takes O(C log R) time for range size R and test cost C.
| Predicate shape | False, then true. Once true, true for every larger x |
|---|---|
| Update rule | P(mid) true: hi = mid. P(mid) false: lo = mid + 1 |
| Preconditions | lo <= hi and P(hi) is true |
| Time | O(C log R), C = cost of one P call, R = hi - lo + 1 |
| Extra space | O(1), excluding the predicate |
This lesson builds on ordinary binary search and binary-search boundary variants.
In ordinary binary search, you compare a target with an array value. Here, there may be no array. Search an ordered integer domain and ask a yes-or-no question about each integer.
Let P(x) mean “integer x is feasible.”
Use predicates with this shape:
P(x) becomes true, it remains true for every larger integer in the domain.This is the false-then-true monotone property.
Return the first integer in the true region.
Before using this algorithm, verify two facts:
P is monotone over the supplied domain.P(hi) must be true.The search domain is inclusive: [lo, hi]. Both endpoints are candidates.
Find the smallest integer x in [0, 20] such that:
Define the predicate:
Inspect the boundary around the answer:
x | x * x | P(x) |
|---|---|---|
| 5 | 25 | false |
| 6 | 36 | true |
So the answer should be 6.
The predicate has this pattern:
P(0) through P(5) are false.P(6) through P(20) are true.A true result at one integer guarantees true results to its right. Each midpoint test can discard half of the candidate integers.
Start with every integer from 0 through 20 as a possible answer.
First x in [0, 20] with x * x >= 30: mid 10 true, 5 false, 8 true, 7 true, 6 true. The interval shrinks [0, 20] to [0, 10], [6, 10], [6, 8], [6, 7], [6, 6]; answer 6.
Inspect the midpoint repeatedly:
When P(mid) is true, mid may be the first true value. Keep it by setting hi = mid.
When P(mid) is false, mid cannot be the answer. The first true value must be strictly to its right, so set lo = mid + 1.
| State | lo | hi | mid | Predicate result | Retained candidate interval |
|---|---|---|---|---|---|
| 0 | 0 | 20 | 10 | P(10) is true because 100 >= 30 | [0, 10] |
| 1 | 0 | 10 | 5 | P(5) is false because 25 < 30 | [6, 10] |
| 2 | 6 | 10 | 8 | P(8) is true because 64 >= 30 | [6, 8] |
| 3 | 6 | 8 | 7 | P(7) is true because 49 >= 30 | [6, 7] |
| 4 | 6 | 7 | 6 | P(6) is true because 36 >= 30 | [6, 6] |
| 5 | 6 | 6 | — | Search ends | Return 6 |
The updates are asymmetric:
mid.mid.The boundary answer remains in the interval.
The interval preserves these facts throughout the search:
[lo, hi].lo has already been established false.hi can still be the first true value.These facts form the loop invariant.
After State 1, [lo, hi] = [6, 10].
6, including 0 through 5, are known false.10 is true, so the interval still contains a true value.Consider each midpoint outcome.
P(mid) is trueThe first true value is at mid or somewhere to its left.
It cannot be only to the right of mid, because mid is already true. Retain the left portion, including mid:
1hi = midP(mid) is falseThe first true value must be strictly right of mid.
mid is false, and every smaller value is also false because the predicate has a false-then-true shape. Exclude mid and everything left of it:
1lo = mid + 1Construct the procedure as follows:
[lo, hi].P(hi) is true, so a solution exists.mid.P(mid).[lo, mid].[mid + 1, hi].lo == hi, one candidate remains.The interval holds the answer candidate. No separate variable named answer is needed.
The search is over integer values, so midpoint rounding must produce an integer. Using:
keeps mid within the current interval.
firstTrue does not mutate the caller’s lo or hi values. It uses local boundary variables. The caller supplies the predicate, which should return a Boolean result without changing the search domain.
11 function firstTrue(lo, hi, predicate) -> integer
22 input:
33 lo, hi: integers defining an inclusive domain [lo, hi]
44 predicate(x): returns true or false for an integer x
55 preconditions:
66 lo <= hi
77 predicate is false-then-true on [lo, hi]
88 predicate(hi) is true
99 mutation behavior:
1010 does not mutate the caller's domain values
1111 returns:
1212 the smallest integer x in [lo, hi] for which predicate(x) is true
1313
1414 while lo < hi
1515 mid = lo + floor((hi - lo) / 2)
1616
1717 if predicate(mid) is true
1818 hi = mid
1919 else
2020 lo = mid + 1
2121
2222 return loThe helper contract is:
1predicate(x) -> Boolean
2
3Input:
4 x is an integer in [lo, hi].
5
6Output:
7 false or true.
8
9Required property:
10 If predicate(x) is true, then predicate(y) is true for every
11 integer y in [x, hi].For the board example:
1predicate(x) = (x * x >= 30)Use:
1firstTrue(0, 20, predicate)
2predicate(x) = (x * x >= 30)The preconditions hold:
0 <= 20.5 and true from 6 onward.predicate(20) is true because 400 >= 30.| Step | Executed lines | lo | hi | mid | Predicate evaluation | Change |
|---|---|---|---|---|---|---|
| Start | 14 | 0 | 20 | — | lo < hi is true | Enter loop |
| State 0 | 15, 17, 18 | 0 | 10 | 10 | P(10) is true because 100 >= 30 | Set hi = 10 |
| State 1 | 15, 17, 20 | 6 | 10 | 5 | P(5) is false because 25 < 30 | Set lo = 6 |
| State 2 | 15, 17, 18 | 6 | 8 | 8 | P(8) is true because 64 >= 30 | Set hi = 8 |
| State 3 | 15, 17, 18 | 6 | 7 | 7 | P(7) is true because 49 >= 30 | Set hi = 7 |
| State 4 | 15, 17, 18 | 6 | 6 | 6 | P(6) is true because 36 >= 30 | Set hi = 6 |
| End | 14, 22 | 6 | 6 | — | lo < hi is false | Return 6 |
At the final check, the interval contains exactly one integer: [6, 6].
Line 22 returns 6.
Prove two facts:
P(lo) is true.Let the first true value in the original domain be a.
Before the loop begins, the candidate interval is the full domain [lo, hi].
A true value exists because predicate(hi) is required to be true. Therefore the first true value a exists and lies in [lo, hi].
There are no domain values below the initial lo, so every value below lo is established false automatically.
Also, hi can still be the first true value because it is true and has not been discarded.
The invariant holds before the first iteration.
predicate(mid) is trueSuppose the invariant holds at the start of an iteration.
If predicate(mid) is true, then the first true value cannot be strictly right of mid. A true value already occurs at mid.
Therefore a lies in [lo, mid].
The algorithm assigns:
1hi = midSo a remains in the new interval. No value below lo changes, so all values below lo remain established false. The new hi is mid, which is true and can still be the first true value.
The invariant is preserved.
predicate(mid) is falseSuppose the invariant holds at the start of an iteration.
If predicate(mid) is false, mid cannot be the first true value. Because the predicate is false-then-true, every value at or below mid is false.
Therefore the first true value must lie in [mid + 1, hi].
The algorithm assigns:
1lo = mid + 1So a remains in the new interval. Every value below the new lo is known false. The value hi remains a possible first true value.
The invariant is preserved.
The loop stops when:
1lo == hiThe invariant says the first true value lies in [lo, hi]. Since that interval has one value, the first true value must be lo.
The invariant also says every domain value below lo is false.
Therefore:
predicate(lo) is true.So line 22 returns exactly the smallest integer for which the predicate is true.
Let:
be the number of candidate integer values in the initial inclusive domain.
Each loop iteration performs:
After each predicate result, the candidate interval is reduced by about half. Therefore the loop performs:
predicate evaluations.
Let one predicate evaluation cost C time. The total time is:
For the example predicate:
1x * x >= 30One evaluation uses a constant amount of work, so C = O(1). The total time is:
The procedure stores only lo, hi, and mid, apart from anything the predicate itself uses. Its auxiliary space is:
excluding space used internally by predicate.
Incorrect assumption:
1A true midpoint means every larger value is true.Exposing input:
1domain = [0, 4]
2P(x) = (x == 1 or x == 3)The predicate values are:
x | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
P(x) | false | true | false | true | false |
The predicate is not false-then-true. For example, P(3) is true but P(4) is false.
A true midpoint does not justify treating all larger values as true. The interval reasoning used by the algorithm no longer applies.
Correction: establish false-then-true monotonicity before using firstTrue.
Incorrect line:
1if predicate(mid) is true
2 hi = mid - 1Exposing input:
1find the smallest x in [0, 20] such that x * x >= 30At the point where:
1lo = 6
2hi = 7
3mid = 6predicate(6) is true because 36 >= 30.
The incorrect update sets:
1hi = 5The update discards 6, even though 6 is the answer. It can also make lo > hi, leaving no valid candidate interval.
Correction:
1hi = midA true midpoint may be the first true value, so it must remain in the interval.
Incorrect assumption:
1Return hi after the loop without checking that any true value exists.Exposing input:
1domain = [0, 20]
2P(x) = (x * x >= 401)Even the largest domain value fails:
1P(20) = (400 >= 401) = falseReturning 20 would be wrong because P(20) is false.
Correction: require predicate(hi) to be true before using this version of the algorithm, or define and implement a separate no-solution result.
These inputs verify the endpoints and small domains:
| Domain and predicate | Expected result | Reason |
|---|---|---|
[0, 20], x * x >= 0 | 0 | The first domain value is true. |
[0, 20], x * x >= 400 | 20 | Only the upper endpoint is the first true value. |
[0, 20], x * x >= 401 | No solution | No domain value is true; reject or use a defined no-solution result. |
[6, 6], x >= 6 | 6 | The one domain value is true. |
[0, 1], x >= 1 | 1 | The false region has one value and the true region has one value. |
Implement:
1firstTrue(lo, hi, predicate)Contract to satisfy:
[lo, hi].lo <= hi.predicate is false-then-true over that domain.predicate(hi) is true.predicate(x) is true.predicate(result) == true.result - 1 is still in the domain, then predicate(result - 1) == false.Executable tests use threshold predicates and square-threshold predicates.
1def first_true(lo, hi, predicate):
2 while lo < hi:
3 mid = lo + (hi - lo) // 2
4 if predicate(mid):
5 hi = mid # mid may be the first true value, keep it
6 else:
7 lo = mid + 1 # mid and everything left of it is false
8 return lo
9
10print(first_true(0, 20, lambda x: x * x >= 30))
11print(first_true(0, 20, lambda x: x * x >= 400))1import java.util.function.IntPredicate;
2
3public class Main {
4 static int firstTrue(int lo, int hi, IntPredicate predicate) {
5 while (lo < hi) {
6 int mid = lo + (hi - lo) / 2;
7 if (predicate.test(mid)) hi = mid; // mid may be the first true value, keep it
8 else lo = mid + 1; // mid and everything left of it is false
9 }
10 return lo;
11 }
12
13 public static void main(String[] args) {
14 System.out.println(firstTrue(0, 20, x -> x * x >= 30));
15 System.out.println(firstTrue(0, 20, x -> x * x >= 400));
16 }
17}1#include <functional>
2#include <iostream>
3using namespace std;
4
5int firstTrue(int lo, int hi, const function<bool(int)>& predicate) {
6 while (lo < hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (predicate(mid)) hi = mid; // mid may be the first true value, keep it
9 else lo = mid + 1; // mid and everything left of it is false
10 }
11 return lo;
12}
13
14int main() {
15 cout << firstTrue(0, 20, [](int x) { return x * x >= 30; }) << endl;
16 cout << firstTrue(0, 20, [](int x) { return x * x >= 400; }) << endl;
17}1function firstTrue(lo, hi, predicate) {
2 while (lo < hi) {
3 const mid = lo + Math.floor((hi - lo) / 2);
4 if (predicate(mid)) hi = mid; // mid may be the first true value, keep it
5 else lo = mid + 1; // mid and everything left of it is false
6 }
7 return lo;
8}
9
10console.log(firstTrue(0, 20, (x) => x * x >= 30));
11console.log(firstTrue(0, 20, (x) => x * x >= 400));Write the check P(x), confirm it flips from false to true once, and pick a range where P(hi) is true. Loop while lo < hi: if P(mid) is true set hi = mid, else set lo = mid + 1. Return lo.
Use it when the answer is a number in a known range and a yes-or-no check is monotone: once a value works, every larger value works. Problems that ask for the smallest feasible value fit this shape.
Find the smallest integer x in [0, 20] with x * x >= 30. P is false for 0 through 5 and true from 6 on. Five midpoint tests, at 10, 5, 8, 7 and 6, narrow the range to 6.
A true midpoint can be the first true value, so it must stay in the range. At lo = 6, hi = 7, mid = 6, the line hi = mid - 1 sets hi to 5 and discards the answer.
The halving argument fails. Take P(x) = (x == 1 or x >= 3) on [0, 4]. The first true value is 1, but the search tests 2, sees false and returns 3. Check monotonicity before you search.