· By John Kavanagh

Binary Search in TypeScript: Keep the Interval Honest

Old books arranged along wooden library shelves.
Image by Daniel Forsman, licensed from Unsplash.

Binary search is short enough to memorise and just awkward enough to punish doing so. Change one comparison, move a pointer to the midpoint rather than past it, and a perfectly reasonable‑looking loop can overlook its last candidate or run forever on two values. Neither failure needs a particularly adventurous input.

I find it easier to begin with the question the two indices answer: which positions could still contain the target? Once that is written down, the loop condition and pointer updates have something concrete to obey. We can then explain the implementation instead of negotiating with three nearly identical versions of it.


The Useful Promise is the Ordering

LeetCode's Binary Search problem gives us an ascending array of unique integers and asks for the target's index, or ‑1 if it is absent. The required runtime is logarithmic. A linear scan would answer the question correctly, but it would inspect every value in the worst case.

Ordering lets one comparison rule out many positions. If the middle value is smaller than the target, every value to its left is also too small. If it is larger, everything to its right is too large. The important operation is discarding a region we have proved cannot help.

Take the values [‑8, ‑3, 1, 4, 7, 12, 19] and a target of 12. Looking at 4 rules out the first four positions together. We haven't checked each of them individually, and we don't need to. Negative values make no difference to that reasoning.


Decide What the Endpoints Mean

I'll use a closed interval: both left and right are possible candidate indices. The initial interval runs from zero to the last index. At the start of every iteration, if the target exists, its index lies somewhere inside that interval.

That statement is the invariant. It is true initially because the interval contains the whole array. Each update must preserve it by removing only impossible positions. When the interval becomes empty, the target cannot be present.

A single remaining index is still worth checking, which is why the loop uses left <= right. When the pointers are equal, there is one candidate, not zero. This is an easy detail to lose if the loop condition is copied from a version whose right endpoint means something else.


The Implementation

The input is read‑only because searching doesn't need to change it. Sorting inside this function would obscure a precondition, add work, and change what the returned index refers to. I want callers to know that they are supplying an already sorted array.

export const binarySearch = (
  values: readonly number[],
  target: number,
): number => {
  let left = 0;
  let right = values.length - 1;

  while (left <= right) {
    const middle = left + Math.floor((right - left) / 2);
    const value = values[middle]!;

    if (value === target) return middle;

    if (value < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return -1;
};

The non‑null assertion on the indexed value follows from the loop bounds. Whenever the loop runs, the midpoint is a valid array index. This assumes an ordinary dense array of finite numbers; TypeScript's readonly annotation doesn't validate runtime input or fill holes in a sparse array.

If the midpoint matches, returning immediately is enough for this problem because the values are unique. Otherwise, the midpoint itself has been ruled out. The next left endpoint is therefore one position after it, or the next right endpoint is one position before it. Keeping the failed midpoint would retain work we have already finished.

Why the Midpoint is Written This Way

Subtracting the left endpoint first gives the distance across the remaining interval. Halving and rounding down keeps the midpoint inside it, then adding the left endpoint translates that offset back into an array index.

For these JavaScript inputs, adding the two indices would also be exact. I still prefer the distance‑based expression because it states the intended geometry and carries well into fixed‑width integer implementations. It doesn't rely on a bitwise shortcut that converts numbers to a narrower integer representation. There is no speed claim hiding in that choice.


Two Traces, Including a Miss

For target 12 in our seven‑value array, the first interval is [0, 6]. Its midpoint is index 3, containing 4, so the next interval is [4, 6]. The midpoint is now index 5, containing 12. We return 5 after two inspected values.

Searching for 6 starts the same way, reaching [4, 6]. This time 12 is too large, so the interval becomes [4, 4]. We must still inspect index 4, containing 7. That is too large too, leaving [4, 3]. The interval is empty, so the answer is ‑1.

Notice that the final pointers in a failed search are allowed to cross. They are bookkeeping for the remaining candidates, not permanently valid positions to read. The loop condition prevents an array access once there are no candidates left.

console.log(binarySearch([-8, -3, 1, 4, 7, 12, 19], 12));  // 5
console.log(binarySearch([-8, -3, 1, 4, 7, 12, 19], 6));  // -1
console.log(binarySearch([7], 7));  // 0
console.log(binarySearch([7], 3));  // -1
console.log(binarySearch([], 7));  // -1

The empty‑array example is a small extension: LeetCode requires at least one element. Here the initial right endpoint is ‑1, the loop never runs, and the result is naturally ‑1. There is no special array access to guard before entering the loop.


A Shrinking Interval is the Termination Proof

Every unsuccessful iteration removes the midpoint and at least one candidate. More strongly, the next interval contains no more than half of the previous interval's candidates, rounded down. The interval size is a non‑negative integer, so it cannot keep shrinking forever.

This catches a common mistake immediately. If the lower endpoint were assigned the midpoint itself, a two‑element interval could keep selecting its leftmost value and remain unchanged. An explanation that only says "move towards the target" would miss that bug; the requirement to shrink the candidate set exposes it.

The runtime is O(log n) for non‑empty input, and the iterative implementation uses O(1) extra space. It allocates no slices and makes no recursive calls. O(1 + log(n + 1)) also accounts for the constant work on an empty input. These are operation counts, not a promise that binary search beats a tiny linear scan in every engine.


Test the Places the Loop Can Fall Off

I check a singleton hit and miss, both endpoints, a missing value between two entries, and targets outside the array's range. My Binary Search Boundary Lab also enumerates small sorted inputs and compares the result with an independent linear scan. Its duplicate‑heavy checks cover the next article's lower and upper bounds.

The lab deliberately tries incorrect endpoint updates and stops them with a bounded execution check. It is useful to see a two‑element counterexample before experimenting on a large input that merely appears to hang. The checks run the same source as these snippets; they don't establish performance across browsers.


Where This Version Stops

With duplicates, this search can return a matching index, but it promises neither the first nor the last one. My guide to finding the first and last matching positions changes the question so equality no longer ends the search.

The same discard‑and‑preserve reasoning also helps with my rotated sorted array walkthrough, where we first establish which half is ordered. In my Koko Eating Bananas article, the candidates are eating speeds instead of indices. Those variants are easier to judge once the endpoints have an explicit meaning. A short loop is a pleasant result; knowing why it stops is the useful part.

Downloadable Resource

  • Binary Search Boundary Lab

    Run my binary search and duplicate‑position examples against linear oracles, then change an endpoint or comparison to see which cases fail.

    Download ZIP

Need a senior engineer involved?

I can work directly in the codebase, review the architecture, or support the team through delivery when the work needs more than extra hands.