Three templates and their invariants

Lesson · 12 min read · Binary search · Introduction to binary search

An exact match, the first true and the last true. Each has its own meaning for lo and hi, and the updates follow from that meaning.

Decide what lo and hi mean

Off-by-one errors in binary search come from writing the updates before deciding what the range means. Fix the meaning first, as an invariant, a statement true before every iteration, and the loop condition, the midpoint and both updates follow from it. Three meanings cover every problem in this chapter.

	Exact match	First true	Last true
Invariant	if the target exists, it is in [lo, hi]	the first true is in [lo, hi]	the last true is in [lo, hi]
Loop while	lo ≤ hi	lo < hi	lo < hi
Midpoint	either rounding	rounded down	rounded up
Test passes	return mid	hi = mid	lo = mid
Test fails	lo = mid + 1 or hi = mid − 1	lo = mid + 1	hi = mid − 1
After the loop	not found	lo is the answer	lo is the answer

"First true" is written here with a closed range whose top candidate is known to pass. When it may not (nothing in the array is large enough), add one candidate past the end, as the next template does.

Exact match

Exact match in a sorted array

search(a, target)

lo = 0, hi = n − 1. If target is anywhere, it is in a[lo..hi].
While lo ≤ hi: mid = lo + (hi − lo) / 2.
If a[mid] = target, return mid. If a[mid] < target, lo = mid + 1. Otherwise hi = mid − 1.
The range is empty: return −1.

Both updates move past mid, because mid has been checked and is not the target. The loop runs while the range has at least one element, which is lo ≤ hi for a closed range.

def search(nums, target):
    lo, hi = 0, len(nums) - 1          # if target is anywhere, it is in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # nums[lo..mid] are all too small
        else:
            hi = mid - 1               # nums[mid..hi] are all too large
    return -1

#include <vector>

int solve(const std::vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;   // if target is anywhere, it is in nums[lo..hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;          // no overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;      // if target is anywhere, it is in nums[lo..hi]
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;      // no overflow
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;    // if target is anywhere, it is in nums[lo..hi]
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

fn solve(nums: &[i64], target: i64) -> i64 {
    // half-open [lo, hi) keeps the indices unsigned: hi = mid never goes below zero
    let (mut lo, mut hi) = (0usize, nums.len());
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if nums[mid] == target {
            return mid as i64;
        }
        if nums[mid] < target { lo = mid + 1 } else { hi = mid }
    }
    -1
}

import Data.Array

solve :: [Int] -> Int -> Int
solve nums target = go 0 (n - 1)
  where
    n = length nums
    a = listArray (0, n - 1) nums
    -- if target is anywhere, it is in a[lo..hi]
    go lo hi
      | lo > hi           = -1
      | a ! mid == target = mid
      | a ! mid < target  = go (mid + 1) hi
      | otherwise         = go lo (mid - 1)
      where mid = lo + (hi - lo) `div` 2

The same code is the reference solution to Find a value in a sorted array, where it is compiled and run against the tests in all six languages.

First true

First index whose element passes

firstTrue(a, test)

lo = 0, hi = n. The answer is in [lo, hi]; hi = n stands for "nothing passes".
While lo < hi: mid = lo + (hi − lo) / 2, rounded down, so mid < hi.
If test(a[mid]), hi = mid: mid may be the first true, so keep it. Otherwise lo = mid + 1.
Return lo.

This is the template to know best. It never checks for equality and never exits early, so there is one exit and one meaning for it. The lower bound, the upper bound, the insertion point, the peak of a mountain and every "smallest value that works" are this loop with a different test.

def search_insert(nums, target):
    lo, hi = 0, len(nums)              # the answer is in [lo, hi); hi = n means "after everything"
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            hi = mid                   # mid passes: the first pass is mid or earlier
        else:
            lo = mid + 1               # mid fails, and so does everything before it
    return lo

#include <vector>

int solve(const std::vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();     // the answer is in [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid; // mid passes
        else lo = mid + 1;                 // mid fails
    }
    return lo;                             // same as std::lower_bound(...) - nums.begin()
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length;          // the answer is in [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) hi = mid; // mid passes
            else lo = mid + 1;                 // mid fails
        }
        return lo;
    }
}

function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;          // the answer is in [lo, hi)
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] >= target) hi = mid;   // mid passes
    else lo = mid + 1;                   // mid fails
  }
  return lo;
}

fn solve(nums: &[i64], target: i64) -> i64 {
    let (mut lo, mut hi) = (0usize, nums.len());   // the answer is in [lo, hi)
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if nums[mid] >= target { hi = mid } else { lo = mid + 1 }
    }
    lo as i64        // the library call: nums.partition_point(|&x| x < target)
}

import Data.Array

solve :: [Int] -> Int -> Int
solve nums target = go 0 n
  where
    n = length nums
    a = listArray (0, n - 1) nums
    -- the answer is in [lo, hi)
    go lo hi
      | lo >= hi            = lo
      | a ! mid >= target   = go lo mid
      | otherwise           = go (mid + 1) hi
      where mid = lo + (hi - lo) `div` 2

The same code is the reference solution to Where a value belongs in a sorted array, where it is compiled and run against the tests in all six languages.

Last true, and why the midpoint rounds up

Maximising problems want the last candidate that passes: the largest x with x² ≤ n, the widest spacing that fits. Now a passing mid must stay in the range, lo = mid, and a failing one goes, hi = mid − 1. With the midpoint rounded down, that pair of updates can stop moving.

The last x with x² ≤ 10, from the range [3, 4]: first with the midpoint rounded down, then rounded up.

Step 1 / 6

lo3hi4
Searching for the last x with x² ≤ 10. Two candidates are left: 3 and 4. The answer is 3.
Step 2 / 6

lo3mid3hi4
mid = 3 + (4 − 3) / 2 = 3, rounded down. 3² = 9 ≤ 10, so mid passes and lo = mid = 3. Nothing has changed.
Step 3 / 6

lo3mid3hi4
Again mid = 3, it passes, lo = 3. The range is still [3, 4].
Step 4 / 6

lo3mid3hi4
Again mid = 3, it passes, lo = 3. The range is still [3, 4], and it always will be: the loop never ends.
Step 5 / 6

lo3mid4hi4
Rounded up instead, mid = 4. 4² = 16 > 10, so hi = mid − 1 = 3. The range has shrunk to [3, 3] and the loop stops at 3.
Step 6 / 6

answer3
With lo = mid on a pass, mid must round up; with hi = mid on a pass, it must round down. Each pairing guarantees the range shrinks.

Last true in code

The integer square root is the smallest complete example: the last r with r² ≤ x, midpoint rounded up as lo + (hi − lo + 1) / 2.

def my_sqrt(x):
    lo, hi = 0, x                      # the answer is in [lo, hi]
    while lo < hi:
        mid = (lo + hi + 1) // 2       # round up, or lo = mid never moves
        if mid * mid <= x:
            lo = mid                   # mid works; the answer is mid or larger
        else:
            hi = mid - 1
    return lo

long long solve(long long x) {
    long long lo = 0, hi = x;              // the answer is in [lo, hi]
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;   // round up, or lo = mid never moves
        if (mid * mid <= x) lo = mid;      // 64-bit: mid < 2^31, so mid * mid < 2^62
        else hi = mid - 1;
    }
    return lo;
}

class Solution {
    public int mySqrt(int x) {
        long lo = 0, hi = x;                   // the answer is in [lo, hi]
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2; // round up, or lo = mid never moves
            if (mid * mid <= x) lo = mid;      // long: no overflow
            else hi = mid - 1;
        }
        return (int) lo;
    }
}

function mySqrt(x) {
  let lo = 0, hi = x;                    // the answer is in [lo, hi]
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);   // round up
    if (mid * mid <= x) lo = mid;        // exact wherever it matters: near x the square is below 2^32
    else hi = mid - 1;
  }
  return lo;
}

fn solve(x: i64) -> i64 {
    let (mut lo, mut hi) = (0i64, x);      // the answer is in [lo, hi]
    while lo < hi {
        let mid = lo + (hi - lo + 1) / 2;  // round up, or lo = mid never moves
        if mid * mid <= x { lo = mid } else { hi = mid - 1 }
    }
    lo
}

solve :: Int -> Int
solve x = go 0 x
  where
    -- the answer is in [lo, hi]; mid rounds up so that lo = mid always moves
    go lo hi
      | lo >= hi        = lo
      | mid * mid <= x  = go mid hi
      | otherwise       = go lo (mid - 1)
      where mid = lo + (hi - lo + 1) `div` 2

The same code is the reference solution to Integer square root without a library, where it is compiled and run against the tests in all six languages.

A last-true search can always be rewritten as a first-true search: the last true is one before the first false. Some people keep a single template and convert. Either habit is fine; mixing them inside one loop is not.