Binary Search is the go-to search for sorted data: instead of scanning one element at a time, it repeatedly cuts the search interval in half.

Looking up a name in a phone book is exactly this process — open to the middle, decide which half, repeat.

Halving at every step means a billion elements need only about 30 comparisons.

How It Works

1. Start with the whole array as the interval [low, high].
2. Compute the middle index mid = ⌊(low + high) / 2⌋.
3. If arr[mid] equals the target, return mid.
4. If the target is smaller than arr[mid], continue in the left half (high = mid - 1).
5. If the target is larger, continue in the right half (low = mid + 1).
6. Repeat until the interval is empty (low > high) — the target isn’t present; return -1.

Key Insight

The correctness rests on one invariant: the target, if present, is always inside [low, high]. Every step either finds it or shrinks the interval while preserving that invariant.

Because each comparison discards half the remaining range, the step count is ⌊log₂(n)⌋ + 1 — the canonical O(log n). The same logic works on any “answer space” where a monotone predicate decides which half is feasible (e.g., finding the first day a machine fails).

Worked Example

Search for 7 in [1, 3, 5, 7, 9, 11, 13]:

• [low=0, high=6], mid=3 → arr[3]=7 → return 3 (found immediately!)

Search for 6 in the same array:

• [0, 6], mid=3 → 7 > 6 → search left: [0, 2]
• [0, 2], mid=1 → 3 < 6 → search right: [2, 2]
• [2, 2], mid=2 → 5 < 6 → search right: [3, 2] — interval empty → return -1

In the visualizer, the highlighted middle column moves and the “active” range shrinks around it each step.

Edge Cases & Pitfalls

• Empty array / low > high — return -1 immediately: the loop never runs.
• Single element — mid is the only candidate: correct hit or correct miss.
• Off-by-one — always use mid = low + (high - low) / 2 (avoids (low + high) / 2 overflow). Update to mid ± 1, never mid, or you loop forever.
• Duplicates — returns some occurrence, not necessarily the first or last. Use lower-bound/upper-bound variants when you need the exact range.
• Unsorted input — the invariant breaks silently and the algorithm returns wrong answers. Sortedness is non-negotiable.

Comparison With Other Searches

Applications

• Lookups in sorted collections — dictionaries, phone books, databases with sorted indexes
• Lower-bound / upper-bound operations (bisect in Python, lower_bound in C++)
• Search on an answer space — “binary search the answer” in problems with a monotone feasibility check

Practice Trajectory

1. Hand-trace Binary Search for target 8 in [2, 4, 6, 8, 10, 12], writing the interval after each step.
2. Explain why the interval shrinks to empty on a miss, and what low > high signals.
3. Implement the lower-bound variant that returns the first index ≥ target.
4. Show why (low + high) / 2 can overflow and how low + (high-low)/2 avoids it.
5. Use binary search on an answer space: find the smallest x where x² ≥ n for n = 50.