Intuition First: The Dictionary Flip#

You'd never look up "serendipity" in a paper dictionary by reading from page 1. You flip to the middle, land on "M", and instantly throw away the entire first half of the book. Flip to the middle of what's left, land on "T" (too far), so you throw away the back half. Each flip halves the pages you still have to consider, so even a 1,000-page dictionary is conquered in about 10 flips.

Binary search is that flip, formalized. And it works for the exact same reason a dictionary does: the entries are sorted. Without sorting, "throw away half" would be meaningless, because the word could be anywhere.

The Problem#

Given a sorted array of integers nums and a target integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log N) runtime complexity.

text

The Core Concept: Divide & Conquer#

Binary Search operates on a simple principle: since the array is already sorted, we can query the middle element.

  • If the middle element matches our target, we are done!
  • If the target is smaller than the middle element, the target must reside in the left half. We can discard the entire right half.
  • If the target is larger than the middle element, the target must reside in the right half. We can discard the entire left half.

By halving our search space at each iteration, we locate the element in logarithmic time.

Code Implementation#

Here is the standard iterative version of Binary Search:

  • Time Complexity: O(log N) as we halve the array size each step.
  • Space Complexity: O(1) auxiliary space for pointers.

Let's take the example in the visualization below: the sorted array [2, 5, 8, 13, 21, 34, 55, 89, 144] with target = 34. Press play and count the probes:

  • Probe 1: low = 0, high = 8, so mid = 4 → 21. Too small. Indices 0..4 dim out and low jumps to 5.
  • Probe 2: mid = 6 → 55. Too large. The right end dims out and high drops to 5.
  • Probe 3: low and high have collapsed onto index 5 → 34. Found.

Nine elements, three comparisons. Watch the two pointer markers close in on each other: everything that dims is a half you never have to look at again.

Binary Search on the Answer#

The trick generalizes further than "find a value in a sorted array". Any time a yes/no question gets easier as you raise the number you're asking about, that monotonic yes/no boundary is itself something you can binary search, even when nothing is stored in an array at all.

The classic example: stations sit along a road at positions [0, 6, 10, 20], and you may add k = 4 new stations anywhere you like. How small can you make the largest gap between neighbours?

The answer is a distance, not an index. So we binary search the distance: pick a candidate d, ask "can 4 extra stations bring every gap under d?" (a simple sum of ceil(gap / d) - 1), and move lo or hi depending on the verdict.

In the visualization below, watch the lo/hi/mid panel at the top: a green mid means the candidate distance is achievable, so hi shrinks toward it; a red mid means it needs more than 4 stations, so lo rises. The interval keeps halving until it pins the answer at roughly 3.33.

What to Remember#

Binary Search is fast. For a list of 4 billion items, it takes at most 32 operations to locate any item or determine its absence.

The requirement is monotonicity, and sortedness is just its most familiar form: in a sorted array, "is the answer to the right of here?" flips from yes to no exactly once. Whenever you can phrase your problem so that some yes/no test flips exactly once along a line (an index, a distance, a capacity), you can binary search it.