Chapter 2: Binary Search
Master binary search from its simplest form to its most creative applications: search sorted arrays in O(log n), generalize the technique to monotonic functions and answer spaces, and handle rotated arrays and unimodal peaks where standard approaches fail.
Chapter Overview
Binary search is one of the most powerful algorithmic techniques you will ever learn. At its core, the idea is simple --- if you can rule out half the remaining candidates with a single comparison, you can find your answer in logarithmic time. On an array of one billion elements, binary search needs at most 30 comparisons.
But binary search is far more than searching a sorted array. Once you understand the underlying principle --- exploiting a monotonic property to halve the search space --- you can apply it to estimation problems, optimization problems, and situations where the "array" is not an array at all but a continuous range of real numbers or an abstract function.
This chapter builds your binary search skill from the ground up. You will start with the classic sorted-array search, then learn to recognize the general pattern: a sequence of values that transitions from one state to another. By the end, you will be able to apply binary search to rotated arrays, mountain arrays, and problems where you are searching for the best answer rather than a specific element.
This chapter covers:
- Vanilla Binary Search: The classic O(log n) search on sorted data
- Sorted Boolean Array: Finding the first True in a monotonic boolean sequence
- Monotonic Function Search: Binary search on answer spaces
- Lower Bound / bisect_left: Finding the first element not smaller than a target
- First Occurrence: Locating the leftmost position of a target value
- Square Root Estimation: Binary search on real numbers with precision control
- Rotated Array Minimum: Searching arrays with a single rotation point
- Peak Finding: Locating the maximum in a unimodal array
Chapter Roadmap
Click any topic to jump in
Vanilla Binary Search
The halving principle: a single invariant — target $\in [l, r]$ — gives $O(\log n)$ search on any sorted array.
The boolean pattern explicitly abstracts the decision step; answer-space search abstracts what is being searched.
Sorted Boolean Pattern
Generalise from equality to any monotonic predicate: find the first index where $P(i)$ becomes true.
Binary Search on Answer
Instead of searching indices, search the answer space — as long as feasibility is monotone in the answer.
Once you can find one match, variants locate the first, last, or a boundary.
Lower / Upper Bound
Lower-bound and upper-bound variants — the two primitives that build every range query on a sorted array.
First / Last Occurrence
Finding the leftmost or rightmost matching index by continuing the search *past* a match.
Binary Search on Reals
Halving on continuous domains — iteration count is fixed by target precision, not by $n$.
When the array is rotated or unimodal, local information still guides halving.
Rotated Arrays
Recover order from a rotated sorted array by identifying which half is still sorted each step.
Peaks and Slopes
Use the local slope as the decision function — binary search works on any unimodal landscape.
Binary search is the fundamental divide-and-conquer search algorithm. Given a sorted array and a target value, it repeatedly compares the target to the middle element and eliminates half of the remaining elements. This yields O(log n) time complexity, a dramatic improvement over the O(n) linear scan.
The key requirement is that the array must be sorted. If you are given an unsorted collection and need to search it many times, sorting it first (O(n log n)) and then using binary search (O(log n) per query) is far more efficient than repeated linear scans.
In this topic
The Halving Principle
Binary search maintains two pointers, lo and hi, that define the current search range. At each step, it computes mid = (lo + hi) // 2 and compares arr[mid] to the target. If arr[mid] == target, the search is done. If arr[mid] < target, the answer must be in the right half, so lo = mid + 1. If arr[mid] > target, the answer must be in the left half, so hi = mid - 1. Each comparison eliminates roughly half the remaining elements, giving O(log n) total comparisons.
Binary search maintains the invariant if the target exists, it lies in . Each iteration either finds the target or discards half of the range, so the size of the range follows . The number of iterations is the smallest with , i.e. . The recurrence has closed form by the master theorem with .
Search for target = 7 in the sorted array [1, 3, 5, 7, 9, 11, 13]. Trace each step.
Implementation Details and Edge Cases
The loop condition while lo <= hi ensures we check every candidate. When lo > hi, the target is not in the array. A common bug is computing mid = (lo + hi) // 2 with very large integers --- in languages with fixed-size integers this can overflow. The safe formula is mid = lo + (hi - lo) // 2. In Python, integers have arbitrary precision so overflow is not a concern, but using the safe formula is good practice for portability.
The overflow trap: can overflow in languages with fixed-width integers; is safe. The termination invariant depends on whether you use with updates (classic, range shrinks strictly), or with updates (half-open, converges to a single index). Both run in — off-by-one bugs come from mixing them.
What does binary search return when the target is not in the array [2, 4, 6, 8, 10] and target = 5?