Binary Search

How to think about it

Maintain an interval that must contain the answer. Probe the midpoint; discard half based on a monotonic test. Prefer the lower-bound form: lo = 0, hi = n (exclusive), shrink until lo == hi.

Template checklist

1. What is the search space? (indices, values, answer range)
2. What does feasible(mid) mean?
3. Do you want the first true or last true?
4. Handle empty arrays and single-element edge cases.

Complexity baseline

O(log n) time, O(1) space for iterative form.

/** Binary search template: lower-bound, then exact match. */
export function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

/** Binary search template: lower-bound, then exact match. */
export function binarySearch(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}