CodeDifficulty: Intermediate3 min

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

first_true.pypy
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}")
OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)
first index with a value at least 10: 3
first index with a value at least 20: 7
FirstTrue.javajava
import 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);
        }
    }
}
OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)
first index with a value at least 10: 3
first index with a value at least 20: 7
first_true.tsts
function 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}`);
}
OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3
first index with a value at least 10: 3
first index with a value at least 20: 7

All 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.