templates · Binary search

Binary search (lower & upper bound)

  • "First" or "last" position of a value that can repeat
  • "Where would it be inserted?" or "how many elements are < x?"
  • The latest entry at or before a timestamp (floor) in a sorted list

Binary search (exact & bounds)

the one rule

The invariant

Everything left of lo is "false", everything from hi on is "true"; when they meet, lo is the first true.

write it from memory

The template

lower bound: first >= target

javajava.util.*
/** First index i with nums[i] >= target (nums.length if none). Half-open range [lo, hi). */static int lowerBound(int[] nums, int target) {    int lo = 0, hi = nums.length;                     // hi = n: "none" is a valid answer    while (lo < hi) {                                 // stop when lo == hi        int mid = lo + (hi - lo) / 2;        if (nums[mid] >= target) hi = mid;            // mid could be the answer: keep it        else lo = mid + 1;                            // mid is too small: drop it    }    return lo;                                        // lo == hi == the first "true"}

Half-open [lo, hi) with hi = n. When the condition is true, hi = mid keeps mid, because mid might be the answer.

fill in the blanks — only these lines change per problem

  1. line 3The range: [0, n) for indices. Keep hi = n so "not found" has a place to land.
  2. line 6The yes/no question that is false…false, true…true. nums[mid] >= target here.
  3. line 9What lo means for your problem: insert position, count of smaller items, or a candidate to check.

upper bound: first > target

javajava.util.*
/** First index i with nums[i] > target. Only the condition changes. */static int upperBound(int[] nums, int target) {    int lo = 0, hi = nums.length;    while (lo < hi) {        int mid = lo + (hi - lo) / 2;        if (nums[mid] > target) hi = mid;        else lo = mid + 1;    }    return lo;}

Identical except > instead of >=. upperBound - lowerBound is how many times target appears.

first and last position

javajava.util.*
/** First and last position of target, or {-1, -1}. Two bounds, nothing new. */static int[] firstAndLast(int[] nums, int target) {    int first = lowerBound(nums, target);    if (first == nums.length || nums[first] != target) return new int[] {-1, -1};    return new int[] {first, upperBound(nums, target) - 1};}

The last position of x is just upperBound(x) - 1. No second, different binary search needed.

fill in the blanks — only these lines change per problem

  1. line 4Always check first < n and nums[first] == target before trusting the bound.

complexity

What it costs

time O(log n)
The range [lo, hi) halves on every step until it is empty.
space O(1)
Just lo, hi and mid.

watch out

Common bugs

  • Writing hi = mid - 1 in the half-open version. That can throw away the answer itself.
  • Reading nums[lo] without checking lo < n. When every element is smaller, lo is n and the read crashes.
  • Using while (lo <= hi) with hi = mid: when lo == hi and the condition is true, hi = mid changes nothing and the loop never ends.

use it

Practise it on

learn it properly