04. Binary Search

TL;DR

Repeatedly halve a search space using a comparison-driven cut—classic indices on sorted arrays, boundary searches (lower_bound / upper_bound), answer ranges where monotonic feasibility lets you check mid, and rotated arrays where a predicate splits into two monotonic pieces. Keep an explicit invariant on what the final low / high represents.

Recognition Cues

• Phrases: "sorted", "first position such that …", "minimum possible …", "feasible capacity / speed", "rotated sorted array", "O(log n)".
• Shapes: sorted vector; implicit sorted domain ([minAnswer, maxAnswer]); matrix rows sorted or sorted-with-offset.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

Binary search is maintaining a shrinking interval [low, high] where the answer is known to lie. For indices, pick mid = low + (high-low)/2 (avoids overflow), compare, discard half. For boundaries, narrow until low == high or use half-open semantics consistently. For search on answer, check(mid) is monotone: if feasible at mid, try lower; else try higher.

Generic Recipe

1. Classic sorted key: low, high index bounds; compare values[mid] to target; shrink half; watch duplicate values and inclusive/exclusive ends.
2. lower_bound (first index where values[index] >= target): adjust so invalid region shrinks; pick assignment branch that keeps definition.
3. upper_bound (first where values[index] > target): same framework with strict inequality on acceptance.
4. Search on answer: set [minAnswer, maxAnswer]; mid = low + (high-low)/2; if feasible(mid) then high = mid else low = mid + 1 (or symmetric)—match open/closed interval style.
5. Rotated array: single-pivot split—compare values[mid] to values[high] or values[low] to know which side is sorted, then decide if target lies in sorted half.

Complexity

• Time: (O(\log n)) for array length (n); answer search over range (R) is (O(\log R \cdot \text{cost of check})).
• Space: (O(1)) iterative; (O(\log n)) if recursive.

Generic Code Template

Go

package main

// Invariant: index of target if present, else insertion index (lower_bound style).
// Loop ends with low == first position where values[index] >= target (for this variant).
func lowerBound(values []int, target int) int {
	low := 0
	high := len(values)
	for low < high {
		mid := low + (high-low)/2
		if values[mid] < target {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return low
}

// Classic sorted index search returning index or -1.
func binarySearchIndex(values []int, target int) int {
	low := 0
	high := len(values) - 1
	for low <= high {
		mid := low + (high-low)/2
		switch {
		case values[mid] == target:
			return mid
		case values[mid] < target:
			low = mid + 1
		default:
			high = mid - 1
		}
	}
	return -1
}

// Search on answer: minimal capacity such that check passes (monotone feasibility).
func minFeasibleCapacity(maxCapacity int, check func(int) bool) int {
	low := 1
	high := maxCapacity
	for low < high {
		mid := low + (high-low)/2
		if check(mid) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func main() {}

JavaScript

// lower_bound: first index where values[index] >= target. Half-open [0, length).
function lowerBound(values, target) {
  let low = 0;
  let high = values.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (values[mid] < target) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return low;
}

// Rotated sorted array, distinct elements: return index of target or -1.
function searchRotated(values, target) {
  let low = 0;
  let high = values.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (values[mid] === target) {
      return mid;
    }
    const leftSorted = values[low] <= values[mid];
    if (leftSorted) {
      if (values[low] <= target && target < values[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      if (values[mid] < target && target <= values[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
}

Variants

• Vanilla — exact match on fully sorted unique or duplicate handling by problem.
• lower_bound / upper_bound — insertion point, range equal to target, "first bad version" style predicates.
• Binary search on answer — Koko eating bananas, capacity to ship, split array largest sum: monotone feasible(mid).
• Rotated / peak / split arrays — compare endpoints to decide which half is ordered; watch duplicates breaking purity (special cases).

Representative Problems

• 704. Binary Search — classic index halving
• 035. Search Insert Position — lower_bound insertion index
• 875. Koko Eating Bananas — search on answer with feasibility check
• 033. Search in Rotated Sorted Array — rotated partition logic
• 004. Median of Two Sorted Arrays — partition binary search (advanced)

Anti-patterns

• Using mid = (low + high) / 2 in languages where overflow matters—prefer low + (high-low)/2.
• Mixing inclusive high with half-open recipes—pick one convention per problem.
• low = mid / high = mid without guarding against infinite loops—ensure interval strictly shrinks (often mid offsets by 1 on one branch).
• Rotated array with duplicates — naive half comparisons can fail; fall back to linear shrink or dedicated predicates.