Binary Search

Binary search is not “search in sorted array.”
Binary search is boundary finding in a monotonic space.

If you internalize that sentence, most advanced binary-search problems become straightforward.

Monotonicity First, Code Second

A binary-search-ready problem has a monotonic property:

• false false false true true true
• or true true true false false false

Your job is to find the transition boundary.

Sorted arrays are one instance. Feasibility functions over answer space are another.

Interval Conventions (Pick One, Stay Consistent)

Most bugs come from mixing interval styles.

Convention A: closed interval [l, r]

• init: l = 0, r = n - 1
• loop: while (l <= r)
• left half: r = mid - 1
• right half: l = mid + 1

Convention B: half-open interval [l, r)

• init: l = 0, r = n
• loop: while (l < r)
• left half: r = mid
• right half: l = mid + 1

Both are valid. Never mix updates across conventions.

Classic Exact Search (Closed Interval)

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

  while (l <= r) {
    const mid = l + Math.floor((r - l) / 2)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return -1
}

Why compute mid as l + (r - l) / 2

In fixed-width integer languages this avoids overflow. In JS overflow is less relevant here, but this formula is still a good habit.

Lower Bound and Upper Bound (Most Useful in Practice)

Lower bound

First index i such that nums[i] >= target.

function lowerBound(nums: number[], target: number): number {
  let l = 0
  let r = nums.length // [l, r)

  while (l < r) {
    const mid = l + Math.floor((r - l) / 2)
    if (nums[mid] >= target) r = mid
    else l = mid + 1
  }
  return l
}

Upper bound

First index i such that nums[i] > target.

function upperBound(nums: number[], target: number): number {
  let l = 0
  let r = nums.length

  while (l < r) {
    const mid = l + Math.floor((r - l) / 2)
    if (nums[mid] > target) r = mid
    else l = mid + 1
  }
  return l
}

Frequency of target

count = upperBound(nums, x) - lowerBound(nums, x)

Predicate Binary Search: First True / Last True

This is the generalized form you should memorize.

First true

Assume predicate is:

• false on [0..k-1]
• true on [k..n-1]

function firstTrue(n: number, pred: (i: number) => boolean): number {
  let l = 0
  let r = n // [l, r)

  while (l < r) {
    const mid = l + Math.floor((r - l) / 2)
    if (pred(mid)) r = mid
    else l = mid + 1
  }
  return l // may be n (no true)
}

Last true

Assume predicate:

• true on [0..k]
• false on [k+1..n-1]

function lastTrue(n: number, pred: (i: number) => boolean): number {
  let l = -1
  let r = n // invariant: pred(l)=true, pred(r)=false (virtual sentinels)

  while (l + 1 < r) {
    const mid = l + Math.floor((r - l) / 2)
    if (pred(mid)) l = mid
    else r = mid
  }
  return l
}

Sentinel form is powerful and reduces off-by-one mistakes.

Binary Search on Answer (Feasibility Search)

Many problems ask min/max feasible value, not an index.

Pattern:

1. define answer range [low, high]
2. define can(x) monotonic predicate
3. binary search boundary

Example: ship packages within D days (minimum capacity)

function shipWithinDays(weights: number[], days: number): number {
  let l = Math.max(...weights)
  let r = weights.reduce((a, b) => a + b, 0)

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

function canShip(weights: number[], days: number, cap: number): boolean {
  let used = 1
  let load = 0

  for (const w of weights) {
    if (load + w > cap) {
      used++
      load = 0
    }
    load += w
  }
  return used <= days
}

Monotonicity:

• if capacity c works, any c' > c also works

That monotonicity is the reason binary search is valid.

Rotated Sorted Array

At each step, one half is sorted.

function searchRotated(nums: number[], target: number): number {
  let l = 0
  let r = nums.length - 1

  while (l <= r) {
    const mid = l + Math.floor((r - l) / 2)
    if (nums[mid] === target) return mid

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

Duplicate caveat

If duplicates exist, nums[l] == nums[mid] == nums[r] can destroy sorted-half certainty.
Typical fallback: shrink edges (l++, r--) which may degrade worst-case to O(n).

Binary Search in Matrix (Flattened View)

If matrix rows are sorted and each row’s first element > previous row’s last element, treat matrix as 1D sorted array.

function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length
  const cols = matrix[0].length
  let l = 0
  let r = rows * cols - 1

  while (l <= r) {
    const mid = l + Math.floor((r - l) / 2)
    const val = matrix[Math.floor(mid / cols)][mid % cols]
    if (val === target) return true
    if (val < target) l = mid + 1
    else r = mid - 1
  }
  return false
}

Index mapping:

• row = Math.floor(idx / cols)
• col = idx % cols

Continuous Binary Search (Real Numbers)

Sometimes answer is real-valued (precision epsilon), e.g., square root, geometric threshold.

function sqrtApprox(x: number): number {
  let l = 0
  let r = Math.max(1, x)
  const EPS = 1e-7

  while (r - l > EPS) {
    const mid = (l + r) / 2
    if (mid * mid >= x) r = mid
    else l = mid
  }
  return r
}

For float binary search, terminate by precision, not index equality.

Correctness Checklist

Before coding:

1. What is monotonic? (array value, predicate, feasibility)
2. What boundary do I need? (exact / first >= / first > / first true / last true)
3. Which interval style am I using? ([l, r] or [l, r))
4. What do I return when target not found?

After coding:

1. test n = 0
2. test n = 1
3. test all equal values
4. test target below min and above max
5. test duplicates for boundary queries

Common Traps

Interview Communication Script

Say:

1. “I am searching the first index where predicate becomes true.”
2. “Invariant: answer is always in current search interval.”
3. “Each iteration halves interval, so O(log n).”

That shows reasoning maturity beyond rote template use.

Problem Ladder

Easy

• Binary Search
• Search Insert Position
• Guess Number Higher or Lower

Medium

• Find First and Last Position of Element in Sorted Array
• Search in Rotated Sorted Array
• Find Peak Element
• Koko Eating Bananas
• Capacity To Ship Packages Within D Days

Hard / high-signal

• Median of Two Sorted Arrays
• Split Array Largest Sum
• Minimize Max Distance to Gas Station (float binary search)

Complexity Summary

Final Takeaway

Binary search is boundary logic on monotonic structure.

If you can:

1. define monotonic predicate,
2. choose correct boundary target,
3. maintain interval invariant cleanly,

you can solve most binary-search interview problems reliably and without off-by-one panic.