Card 03/ 08
The First-True Template in Python, Java and TypeScript
One loop that halves [low, high] by testing mid, with the predicate and the two moves marked.
The first-true template takes the number of candidates and a predicate, and returns the first candidate for which the predicate is true, or n when none is. The highlighted lines are the ones that change between problems: the range the search starts with, and the predicate it tests at mid. Each listing searches 2 4 7 10 10 13 18 for the first value at least 10, then for the first value at least 20.
The first-true template in three languages
def first_true(n: int, is_true) -> int:
low, high = 0, n
while low < high:
mid = low + (high - low) // 2
if is_true(mid):
high = mid
else:
low = mid + 1
return low
values = [2, 4, 7, 10, 10, 13, 18]
for target in (10, 20):
index = first_true(len(values), lambda i: values[i] >= target)
print(f"first index with a value at least {target}: {index}")first index with a value at least 10: 3
first index with a value at least 20: 7import java.util.function.IntPredicate;
public class FirstTrue {
static int firstTrue(int n, IntPredicate isTrue) {
int low = 0;
int high = n;
while (low < high) {
int mid = low + (high - low) / 2;
if (isTrue.test(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
public static void main(String[] args) {
int[] values = {2, 4, 7, 10, 10, 13, 18};
for (int target : new int[] {10, 20}) {
int index = firstTrue(values.length, i -> values[i] >= target);
System.out.println("first index with a value at least " + target + ": " + index);
}
}
}first index with a value at least 10: 3
first index with a value at least 20: 7function firstTrue(n: number, isTrue: (index: number) => boolean): number {
let low = 0;
let high = n;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (isTrue(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
const values = [2, 4, 7, 10, 10, 13, 18];
for (const target of [10, 20]) {
const index = firstTrue(values.length, (i) => values[i] >= target);
console.log(`first index with a value at least ${target}: ${index}`);
}first index with a value at least 10: 3
first index with a value at least 20: 7All three print 3 for the first search and 7 for the second: no value is at least 20, so low ends at n, one past the last index, and the caller must check for that before reading values[low]. mid is computed as low + (high − low) / 2 rather than (low + high) / 2, which can overflow a 32-bit int in Java when both are large, as the Binary Search topic in Algorithms shows. Python's // rounds towards negative infinity and Java's / towards zero, but they agree here because low and high are never negative; TypeScript has no integer division, so it needs Math.floor. The template is O(log n) calls to the predicate and O(1) extra space.
← → move through sections and cards