Recap: Binary Search

A sorted range, an invariant, a safe midpoint, and two bounds for repeated values.

Binary search comes down to the seven ideas below, each listed with the card that covers it. One invariant explains all of them: if the target is in the array, it lies between low and high, and every step keeps that true while making the range shorter.

What the topic established, and which card it was on
The idea	Where
Compare with the middle of a sorted range and keep the half that can hold the target; about log2 n + 1 comparisons at most	Binary Search: Halving a Sorted Range
On a miss the bounds cross, and `low` stops at the index where the target would be inserted	Trace a Search for a Value That Is Not There
The target, if present, is always between `low` and `high`; moving to `mid + 1` and `mid - 1` keeps that and ends the loop	The Invariant That Makes Binary Search Correct
In Java `(low + high) / 2` can overflow; write `low + (high - low) / 2`, and floor the division in TypeScript	A Midpoint That Overflows
The lower bound is the first index at least the target, the upper bound the first index above it, and their difference is the count	Lower Bound, Upper Bound and the Insertion Point
Python's `bisect_left` and `bisect_right` are the two bounds, Java's `Arrays.binarySearch` is an exact search, and TypeScript has no built-in	Binary Search in Python, Java and TypeScript
A negative result from `Arrays.binarySearch` is `-(insertion point) - 1`; Python's `bisect` returns the insertion point itself	Reading a Negative Result From Java's binarySearch as Only Not Found

The costs to keep are these, for a sorted array of n items.

Binary search on a sorted array of n items

Best case: O(1); the first middle item is the target
Worst case: O(log n); the target is absent or found last
Extra space: O(1); the loop version
Input: Sorted; by the order the comparisons use

Together they let you trace a search by hand, write one that is correct for present and missing values in Python, Java and TypeScript, and use the two bounds to count, insert and select ranges in sorted data.

← → move through sections and cards