Binary Search

The core idea

Every iteration of binary search eliminates half the remaining candidates. On an array of 1,000,000 elements, you find any element in ≤ 20 comparisons. That’s the power of O(log n).

The requirement: the search space must be monotonic — there’s a point where elements go from “doesn’t satisfy condition” to “satisfies condition”. Sorted arrays are the obvious case, but not the only one.

The safe template

Many binary search bugs come from off-by-one errors. Here’s a template that avoids them:

function binarySearch(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)  // avoids integer overflow
    if (nums[mid] === target) return mid
    if (nums[mid] < target)   left  = mid + 1
    else                      right = mid - 1
  }
  return -1
}

Why left + (right - left) / 2 instead of (left + right) / 2?
In languages with fixed integer size, left + right can overflow. JavaScript doesn’t have this problem (numbers are 64-bit floats), but the habit is worth building.

Why left <= right?
When left === right, there’s exactly one element left to check. We need to inspect it. left < right would skip it.

Left-biased: find the first true

When you want the leftmost index that satisfies a condition (the first position where something flips from false to true):

function findFirst(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1
  let result = -1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) {
      result = mid    // record, but keep searching left
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return result
}

Or with a boolean-predicate style (cleaner for complex conditions):

// Returns the smallest index where pred(index) is true
// Assumes pred is false for [0..x-1] and true for [x..n-1]
function firstTrue(n: number, pred: (i: number) => boolean): number {
  let left = 0, right = n - 1, ans = n
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (pred(mid)) { ans = mid; right = mid - 1 }
    else             left = mid + 1
  }
  return ans
}

Right-biased: find the last true

function lastTrue(n: number, pred: (i: number) => boolean): number {
  let left = 0, right = n - 1, ans = -1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (pred(mid)) { ans = mid; left = mid + 1 }  // record, keep searching right
    else             right = mid - 1
  }
  return ans
}

Classic: search in rotated sorted array

The array [4,5,6,7,0,1,2] was sorted then rotated. Find target.

The key insight: at least one half of the array is always sorted. Check which half, then decide where to search.

function searchRotated(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) return mid

    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (nums[left] <= target && target < nums[mid]) right = mid - 1
      else                                             left  = mid + 1
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) left  = mid + 1
      else                                              right = mid - 1
    }
  }
  return -1
}

Beyond sorted arrays: binary search on the answer

Sometimes the array isn’t sorted but the answer space is monotonic. Classic example: “What’s the minimum capacity to ship packages within D days?”

function shipWithinDays(weights: number[], days: number): number {
  // Answer must be between max(weights) and sum(weights)
  let left  = Math.max(...weights)
  let right = weights.reduce((a, b) => a + b, 0)

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (canShip(weights, days, mid)) right = mid  // try smaller
    else                              left  = mid + 1
  }
  return left
}

function canShip(weights: number[], days: number, capacity: number): boolean {
  let daysNeeded = 1, load = 0
  for (const w of weights) {
    if (load + w > capacity) { daysNeeded++; load = 0 }
    load += w
  }
  return daysNeeded <= days
}

The insight: “can we do this with capacity c?” is monotonic — once it becomes true, it stays true as c increases. Binary search on that.

Common traps

Complexity