Binary Search

Binary search works by maintaining a window [lo, hi] that is guaranteed to contain the target if it exists. On each step the algorithm checks the midpoint and shrinks the window by half, reaching an answer in O(log n) comparisons.

Invariants

Two invariants hold throughout every iteration:

1. If the target exists, it lies within arr[lo..hi] (inclusive).
2. Every element outside [lo, hi] has been ruled out.

When lo > hi the window is empty and the target is absent.

The Safe Midpoint Formula

In languages with fixed-width integers (Java, C++), Math.floor((lo + hi) / 2) can overflow when lo + hi exceeds the maximum integer. JavaScript numbers are IEEE-754 doubles with 53-bit mantissas, so overflow is not a practical concern for array indices — but the safer form is still good practice and communicates intent clearly:

const mid = Math.floor(lo + (hi - lo) / 2);

(hi - lo) is always non-negative inside the loop, so this expression is always safe regardless of the language or environment.

Classic Implementation

function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);

    if (arr[mid] === target) return mid;  // found
    if (arr[mid] < target)  lo = mid + 1; // target is to the right
    else                    hi = mid - 1; // target is to the left
  }

  return -1; // not found
}

const sorted = [1, 3, 5, 7, 9, 11, 13];
binarySearch(sorted, 7);  //  3
binarySearch(sorted, 6);  // -1

Complexity

Each iteration halves hi - lo, so the loop runs at most log₂(n) + 1 times.

Returning lo Instead of -1 — Finding the Insertion Point

Sometimes you need to know where a missing value would be inserted to keep the array sorted. When the loop exits, lo is exactly that insertion point.

function lowerBound(arr, target) {
  let lo = 0;
  let hi = arr.length; // note: hi = length, not length - 1

  while (lo < hi) {    // note: strict < so hi is exclusive
    const mid = Math.floor(lo + (hi - lo) / 2);

    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid;
  }

  return lo; // index of first element >= target
}

lowerBound([1, 3, 5, 7, 9], 6); // 3  (would insert before index 3)
lowerBound([1, 3, 5, 7, 9], 5); // 2  (first position of 5)

The two variants — return -1 for existence queries and return lo for insertion-point queries — follow the same core structure. The only differences are the boundary conditions (hi = length, lo < hi) and the final return.

Common Pitfalls

• Using arr.length - 1 as hi when computing insertion point — the insertion index can be arr.length itself (appending to the end), so hi must start at arr.length.
• Forgetting + 1 after lo = mid or - 1 after hi = mid in the standard variant, causing an infinite loop when lo === hi.

Up Next

The binary search idea extends beyond index lookups — you can binary search on the answer space to solve optimization problems.