templates · Binary search

Binary search (exact match)

  • The input is sorted and you need one exact value
  • "Must run in O(log n)"
  • A sorted structure you can index, like a matrix read row after row

Binary search (exact & bounds)

the one rule

The invariant

If the target is anywhere, it is inside nums[lo..hi]; each step throws away the half that cannot hold it.

write it from memory

The template

closed range [lo, hi]

javajava.util.*
/** Index of target in a sorted array, or -1. Closed range: we search nums[lo..hi]. */static int search(int[] nums, int target) {    int lo = 0, hi = nums.length - 1;                 // both ends are still possible    while (lo <= hi) {                                // range not empty        int mid = lo + (hi - lo) / 2;                 // no (lo + hi) overflow        if (nums[mid] == target) return mid;        if (nums[mid] < target) lo = mid + 1;         // answer is right of mid        else hi = mid - 1;                            // answer is left of mid    }    return -1;                                        // range empty: not there}

Closed range means hi = n - 1, while (lo <= hi) and mid ± 1. Keep all three together and it never loops forever.

fill in the blanks — only these lines change per problem

  1. line 3The search range: indices 0..n-1, or a range of values for "search on the answer".
  2. line 6The match test. For a custom check (first bad version) this becomes "record and keep going".
  3. line 7When the answer must be right of mid: here, nums[mid] < target.
  4. line 10What to return when it is not there: -1, or lo (where it would be inserted).

a matrix as one sorted array

javajava.util.*
/** Search a matrix whose rows, read one after another, are sorted. Treat it as one array of rows × cols. */static boolean searchMatrix(int[][] matrix, int target) {    if (matrix.length == 0 || matrix[0].length == 0) return false;    int rows = matrix.length, cols = matrix[0].length;    int lo = 0, hi = rows * cols - 1;    while (lo <= hi) {        int mid = lo + (hi - lo) / 2;        int value = matrix[mid / cols][mid % cols];   // index → (row, col)        if (value == target) return true;        if (value < target) lo = mid + 1;        else hi = mid - 1;    }    return false;}

Same loop. Only the read changes: index mid lives at row mid / cols, column mid % cols.

fill in the blanks — only these lines change per problem

  1. line 8How one index maps to your structure: here (mid / cols, mid % cols).

complexity

What it costs

time O(log n)
Each step halves the range: 10⁶ elements need about 20 steps (2²⁰ ≈ 10⁶).
space O(1)
Three ints: lo, hi and mid.

watch out

Common bugs

  • int mid = (lo + hi) / 2 overflows when lo + hi passes 2³¹ − 1. Write lo + (hi - lo) / 2.
  • Mixing styles: while (lo < hi) with hi = mid - 1 skips elements. Pick closed [lo, hi] or half-open [lo, hi) and stick to it.
  • Running it on unsorted input. Binary search needs an order that tells you which half to drop.

use it

Practise it on

learn it properly