Modified Binary Search: Finding Where a Condition Turns True

Modified binary search finds the first candidate for which a yes-or-no test is true, provided the test is false for every candidate before that point and true for every one after it. The test is called the predicate, and a predicate that changes only once, from false to true, is called monotone. The cue is that property, not a sorted array: the candidates can be the indices of an array, the builds of a program, or the possible answers to a question. Binary search on a sorted array, as the Binary Search topic in Algorithms teaches it, is one case, where the predicate is "the value here is at least the target".

The search keeps one invariant: the first true candidate lies in the range from low to high, where high starts one past the last candidate in case none is true. Each round tests the middle candidate, mid. If the predicate is true at mid, the answer is mid or earlier, so high moves to mid; if it is false, the answer is after mid, so low moves to mid + 1. The range halves every round, and when low meets high, low is the answer.

Take the values 2 4 7 10 10 13 18 and the predicate "the value is at least 10". Read left to right it gives F F F T T T T, false three times and then true for good.

Three tests settled seven candidates, because each test ruled out half of what was left. For n candidates the search makes about log₂ n tests, so it is O(log n) tests and O(1) extra space; if the predicate itself costs more than O(1), its cost multiplies that count.

Finding the first page of a novel on which a character has arrived works the same way: open the book in the middle, and whether they have appeared yet says which half to keep. The likeness breaks when the character leaves the story and comes back, because the search needs a predicate that never turns false again once it is true. A test that goes F T F T has no single point to find, and binary search on it returns an answer without any warning that it is wrong.