Binary Search

Binary search is an algorithm for finding a target value in a sorted array by repeatedly halving the search range: probe the middle element, discard the half that cannot contain the target, and repeat. Its time complexity is O(log n) — a million-element array is settled in at most twenty comparisons.

You already play this game. Someone picks a number between 1 and 100, you guess 50, they say "higher," and you've just erased half the board without looking at it. Binary search is that guessing game played against an array, and the only thing it demands in return is that the array be sorted — the ordering is what lets "the middle element is 16" tell you something about the half you never inspected.

How Binary Search Works

Keep a window [lo, hi] over the array: the slice still capable of containing the target. Initially lo = 0 and hi = n − 1, inclusive on both ends. Each iteration does three things:

1. Compute the midpoint, mid = (lo + hi) // 2.
2. Compare nums[mid] with target.
3. Act on the verdict. Equal → return mid. nums[mid] < target → the target, if present, sits to the right, so lo = mid + 1. nums[mid] > target → hi = mid − 1.

The ±1 is not decoration. mid was just inspected and acquitted, so the new window excludes it — that exclusion is what guarantees the window shrinks every round. The invariant is the whole proof: if the target is anywhere, it is in nums[lo..hi]. When lo > hi the window is empty while the invariant still holds, so the target cannot exist; return −1.

Binary Search Step by Step

The default input is nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] with target = 23.

1. lo = 0, hi = 9 → mid = 4. nums[4] = 16, and 16 < 23, so the answer lives to the right. Discard indices 0–4; lo = 5. One comparison, half the array gone.
2. lo = 5, hi = 9 → mid = 7. nums[7] = 56 > 23 — too high, exactly like your guessing-game partner saying "lower." Discard indices 7–9; hi = 6.
3. lo = 5, hi = 6 → mid = 5. nums[5] = 23. Match — return index 5.

Ten elements, three probes. Had the target been absent (say 24), the window would have kept collapsing until lo crossed hi, and the algorithm would return −1.

On the canvas, the window's left and right walls march inward while the mid pointer drops onto the center of whatever remains. Every cell outside [lo, hi] fades out — faded means proven irrelevant, which is the entire lesson in one visual: you watch half the array pay the price of a single comparison. The matched cell turns green.

Time and Space Complexity

Space is O(1): the iterative form carries two integer pointers and no recursion stack. The logarithm is the headline — twenty guesses settle a million elements, thirty settle a billion. Doubling the data costs you one extra comparison.

Edge Cases

• Empty array — hi = −1, so lo <= hi fails on entry; return −1 without a single probe.
• Single element — lo = hi = 0; one comparison decides.
• Target at the first or last index — the window shrinks toward that end over ~log n rounds before matching; the extremes are the worst case, not the best.
• Target between two adjacent elements — the window collapses to one cell, the cell fails the comparison, the walls cross, return −1.
• Duplicates — vanilla binary search returns the index of some matching element, not necessarily the first or last; that is the bisect_left / bisect_right variant.

Common Mistakes

• lo = mid instead of lo = mid + 1. When lo and hi are adjacent, mid rounds down to lo, the update changes nothing, and the loop spins forever. The +1 is load-bearing. The player ships this as a mode: switch the variant to lo = mid and the window visibly narrows to two cells, then freezes there — the search never returns.
• lo < hi instead of lo <= hi. The bounds are inclusive; < abandons single-cell windows one iteration early and misses targets sitting in them. Switch the variant to lo < hi and search for the smallest element: the window collapses onto the right cell, the loop exits without checking it, and a present value comes back as "not found."
• Midpoint overflow. In Java or C++, lo + hi can overflow a 32-bit int; write lo + (hi - lo) / 2. Python's integers are arbitrary-precision, so the displayed code is safe as written.
• Running it on unsorted data. A probe can throw away the half that holds the target, so the search can return -1 for a value that is present. An index it does return still points at a real match, because every hit is checked with ==. What you lose is the guarantee: sortedness is the precondition that makes the discarded half safe to discard.
• Using it where a hash set wins. Membership-only queries are O(1) average with a set; binary search earns its keep when you need position — an insertion point, a nearest neighbor — which hashing cannot give you.