What property must a condition have for 'binary search on the answer' to work?

It must be monotonic: false for every value below some point and true for every value from that point on (if speed s works, any faster speed works too). Then the first true value can be found by halving.

Why does the template use `hi = mid` but `lo = mid + 1`?

When the condition is true at mid, mid could be the answer, so it stays in range. When it's false, mid is definitely not the answer, so it is excluded. The range shrinks every iteration, which guarantees termination.

Binary Search (and Searching for an Answer) — DSA Patterns Made Simple

The problem

You have a sorted list of 1,000,000 prices and need to know where 4,999 is, or where it would go. Scanning is up to a million steps. Binary search needs about 20.

How to spot it

The input is sorted (or rotated sorted)
"Find the first / last position where…"
O(log n) is required, or n is huge
Search for an answer: "smallest speed / capacity / size such that it works", where if a value works, every bigger value works too

The idea

Look at the middle. If the target is bigger, throw away the left half; if smaller, the right half. Each step halves the range, so a million items takes about 20 steps.

The most reusable version is "find the first index where condition is true", for a condition that is false, false, …, true, true. Keep lo and hi so the answer is always inside [lo, hi], and stop when they meet. Plain lookup is the special case condition = arr[i] >= target.

The template

def first_true(lo, hi, condition):
    # smallest x in [lo, hi] with condition(x) True (hi if none)
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid          # mid might be the answer: keep it
        else:
            lo = mid + 1      # mid is too small: discard it
    return lo

function firstTrue(lo, hi, condition) {
  // smallest x in [lo, hi] with condition(x) true (hi if none)
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (condition(mid)) hi = mid;   // mid might be the answer: keep it
    else lo = mid + 1;              // mid is too small: discard it
  }
  return lo;
}

Memorise this one shape. hi = mid keeps a possible answer; lo = mid + 1 discards a definite non-answer. Because the range shrinks every step, it can't loop forever.

Worked example

The same first_true function finds where a value is (or would be inserted), and then answers a "search for an answer" question: the slowest eating speed that finishes all piles of bananas within h hours.

One template, three searchesTry it yourself

def first_true(lo, hi, condition):
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def search(nums, target):
    i = first_true(0, len(nums), lambda i: nums[i] >= target)
    return i if i < len(nums) and nums[i] == target else -1


def insert_position(nums, target):
    return first_true(0, len(nums), lambda i: nums[i] >= target)


def min_eating_speed(piles, h):
    def hours(speed):
        return sum((p + speed - 1) // speed for p in piles)   # ceil(p / speed)
    return first_true(1, max(piles), lambda speed: hours(speed) <= h)


nums = [-1, 0, 3, 5, 9, 12]
print("index of 9:", search(nums, 9))
print("index of 2:", search(nums, 2))
print("insert 4 at:", insert_position(nums, 4))
print("slowest speed:", min_eating_speed([3, 6, 7, 11], 8))

Output

index of 9: 4
index of 2: -1
insert 4 at: 3
slowest speed: 4

One template, three searchesTry it yourself

function firstTrue(lo, hi, condition) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (condition(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function search(nums, target) {
  const i = firstTrue(0, nums.length, (i) => nums[i] >= target);
  return i < nums.length && nums[i] === target ? i : -1;
}

function insertPosition(nums, target) {
  return firstTrue(0, nums.length, (i) => nums[i] >= target);
}

function minEatingSpeed(piles, h) {
  const hours = (speed) => piles.reduce((t, p) => t + Math.ceil(p / speed), 0);
  return firstTrue(1, Math.max(...piles), (speed) => hours(speed) <= h);
}

const nums = [-1, 0, 3, 5, 9, 12];
console.log("index of 9:", search(nums, 9));
console.log("index of 2:", search(nums, 2));
console.log("insert 4 at:", insertPosition(nums, 4));
console.log("slowest speed:", minEatingSpeed([3, 6, 7, 11], 8));

Output

index of 9: 4
index of 2: -1
insert 4 at: 3
slowest speed: 4

Search ranges use hi = len(nums) (one past the end) so "bigger than everything" has a valid answer: insert at the end.

Common mistakes

Mixing templates. while lo <= hi with hi = mid - 1 is a different (valid) style; mixing it with hi = mid causes infinite loops. Stick to one.
Binary searching unsorted data. The condition must be false…false, true…true.
Missing the "search for an answer" form. When the answer is a number in a range and bigger always works, binary search the answer itself.
Overflow in other languages. In Java or C++, (lo + hi) / 2 can overflow; use lo + (hi - lo) / 2.

Practice

Binary Search (easy)
Search in Rotated Sorted Array (medium): at each step one half is sorted; check whether the target lies in that half.

Key points

Halving the range gives O(log n): about 20 steps for a million items.
Learn one template: first index where a condition becomes true.
hi = mid keeps a possible answer, lo = mid + 1 drops a non-answer.
Use it to search for answers too ("smallest speed that works").