Chapter 2: Binary Search

Week 2

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.

Topics: 8
Videos: 8
Min read: 31

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

Explainer video

Vanilla Binary Search

The halving principle: a single invariant — target $\in [l, r]$ — gives $O(\log n)$ search on any sorted array.

The Halving PrincipleImplementation Details and Edge Cases

Generalising the condition

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.

The Monotonic Boolean PatternHandling Edge Cases

Binary Search on Answer

Instead of searching indices, search the answer space — as long as feasibility is monotone in the answer.

Binary Search on Answer SpaceDesigning the Feasibility Check

From search to ranges

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.

Lower Bound Binary SearchUpper Bound and Range Queries

First / Last Occurrence

Finding the leftmost or rightmost matching index by continuing the search *past* a match.

Searching Past a MatchLast Occurrence Variant

From integers to reals

Binary Search on Reals

Halving on continuous domains — iteration count is fixed by target precision, not by $n$.

Binary Search on Real NumbersIteration Count and Convergence

From sorted to partially sorted

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.

Identifying the Sorted HalfHandling Duplicates

Peaks and Slopes

Use the local slope as the decision function — binary search works on any unimodal landscape.

Using the Slope to SearchPlateau and Multiple Peaks

Topics

8 topics in this chapter

A phone book holds a million names and you need the number for "Moreno". Reading it front to back could take a million glances, but nobody does that: you open near the middle, see "Lopez", and immediately discard the entire first half. Repeat a few more times and you land on the page after about twenty glances.

The previous chapter ended with sorting, including merge sort, quick sort, and custom comparators, and sorting is exactly what makes this trick possible. Once data is ordered, a single comparison with the middle element tells you which half cannot contain the target. That is binary search: it keeps a shrinking range of candidates and halves it every step, so n elements need only about $\log_2 n$ comparisons, 30 for a billion.

This first topic covers the classic version on a sorted array: the halving loop and its invariant, then the details that make it notoriously easy to get wrong, namely loop conditions, off-by-one updates, midpoint overflow, and what the pointers mean when the target is absent. Every later topic in the chapter is a variation on this loop.

Definition

Binary search finds a target in a sorted array by maintaining a range [lo, hi] that must contain the target if it is present. Each step compares the target with the middle element and discards the half that cannot contain it. It runs in O(log n) time and O(1) extra space, returning the index or a not-found signal.

In this topic

1The Halving Principle
2Implementation Details and Edge Cases

1 of 2

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.

Mathematical Intuition

Binary search maintains the invariant if the target exists, it lies in $[l, r]$ . Each iteration either finds the target or discards half of the range, so the size of the range follows $n, n/2, n/4, \dots, 1$ . The number of iterations is the smallest $k$ with $n/2^k \le 1$ , i.e. $k = \lceil \log_2 n \rceil$ . The recurrence $T(n) = T(n/2) + O(1)$ has closed form $T(n) = O(\log n)$ by the master theorem with $a = 1, b = 2, f(n) = O(1)$ .

Example:

Search for target = 7 in the sorted array [1, 3, 5, 7, 9, 11, 13]. Trace each step.

2 of 2

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.

Mathematical Intuition

The overflow trap: $m = (l + r) / 2$ can overflow in languages with fixed-width integers; $m = l + (r - l) / 2$ is safe. The termination invariant depends on whether you use $l \le r$ with $m \pm 1$ updates (classic, range shrinks strictly), or $l < r$ with $r = m$ updates (half-open, converges to a single index). Both run in $\Theta(\log n)$ — off-by-one bugs come from mixing them.

Example:

What does binary search return when the target is not in the array [2, 4, 6, 8, 10] and target = 5?

Papers

Bentley, J. — Programming Pearls: Writing Correct Programs (1983, Communications of the ACM)

Blogs

Binary Search — CP Algorithms Nearly All Binary Searches and Mergesorts are Broken — Google Research

Definition

A sorted boolean array is a sequence of the form [False, ..., False, True, ..., True], meaning a monotonic predicate evaluated over indices. The task is to return the smallest index holding True, or the length of the array if none does. Binary search solves it in O(log n) predicate evaluations by keeping lo on the False side and hi on the True side.

In this topic

1The Monotonic Boolean Pattern
2Handling Edge Cases

1 of 2

The Monotonic Boolean Pattern

A sorted boolean array has the form [F, F, ..., F, T, T, ..., T]. We want the index of the first True. Binary search works because the array is monotonic: once a True appears, everything to its right is also True. If arr[mid] is True, the first True is at mid or to its left, so hi = mid. If arr[mid] is False, the first True must be to the right, so lo = mid + 1. The loop runs with while lo < hi and returns lo (which equals hi) at the end.

Mathematical Intuition

If a predicate $P: \{0, \dots, n-1\} \to \{\text{false}, \text{true}\}$ is monotone — once it becomes true it stays true — then the set $\{i : P(i)\}$ is a suffix $[k, n-1]$ . Binary search finds $k$ in $O(\log n)$ calls to $P$ . The invariant: $P(l-1) = \text{false}$ and $P(r) = \text{true}$ throughout, so when $l = r$ the index $l$ is exactly the transition point.

Example:

Find the index of the first True in [False, False, False, True, True, True].

2 of 2

Handling Edge Cases

Two edge cases arise: (1) the array is entirely False --- there is no True element, and (2) the array is entirely True --- the first True is at index 0. A clean way to handle both is to initialize hi = len(arr) (one past the end). If the search finishes with lo == len(arr), no True was found. If lo == 0, the first element is True. This sentinel approach avoids special-case checks after the loop.

Mathematical Intuition

Three boundary scenarios: (1) $P$ is false everywhere — return $n$ as a sentinel; (2) $P$ is true everywhere — return $0$ ; (3) array is empty — return $0$ without any probes. All three are handled automatically if you initialise $l = 0, r = n$ (half-open) and maintain the loop condition $l < r$ — the final value of $l$ is the first true index or $n$ .

Example:

Find the first True in [False, False, False, False] (all False) and in [True, True, True] (all True).

Papers

Bentley, J. L. & Yao, A. C.-C. — An Almost Optimal Algorithm for Unbounded Searching (1976, Information Processing Letters)

Blogs

First Bad Version — NeetCode Exponential Search — Wikipedia

Definition

Binary search on the answer applies binary search to a range of candidate answers [lo, hi] instead of an array. It requires a feasibility predicate feasible(x) that is monotonic: once True, it stays True for every larger x in a minimization problem. The smallest feasible x is found with O(log(hi - lo)) evaluations of the predicate.

In this topic

1Binary Search on Answer Space
2Designing the Feasibility Check

1 of 2

Binary Search on Answer Space

Instead of searching an array, you search a range of possible answers. Define a function feasible(x) that returns True if x is a valid answer and False otherwise. If feasible is monotonic (once it becomes True, it stays True for all larger x), then you can binary search on x to find the smallest feasible answer. This technique is sometimes called 'binary search on the answer' and it turns many hard optimization problems into simple feasibility checks.

Mathematical Intuition

When a feasibility function $f(x)$ is monotone in the answer $x$ — e.g., 'can we finish in $\le x$ hours?' — the set of feasible answers is a suffix of the real line. Binary search on $[lo, hi]$ converges to the smallest feasible $x$ in $O(\log(hi - lo) \cdot C_f)$ where $C_f$ is the cost of one feasibility check. This collapses optimisation to search.

Example:

A shipping company needs to deliver packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] in 5 days. What is the minimum ship capacity needed?

2 of 2

Designing the Feasibility Check

The hardest part of binary search on the answer is writing the feasible(x) function. It must be efficient (ideally O(n) or O(n log n)) since it is called O(log(range)) times. The function must also be monotonic: if feasible(x) is True, then feasible(x + 1) must also be True (for minimization problems). Common feasibility checks involve greedy algorithms --- scan through the data and check if the constraint can be satisfied with the given answer.

Mathematical Intuition

For the check $f(x)$ to work, it must be strictly monotone (or at least non-decreasing). Example (Koko bananas): 'can she finish at rate $k$ in $h$ hours?' reduces to $\sum_i \lceil p_i / k \rceil \le h$ . Because $\lceil p_i / k \rceil$ is non-increasing in $k$ , $f$ is monotone: if rate $k$ works, so does any higher rate — exactly the precondition binary search requires.

Example:

Given an array [7, 2, 5, 10, 8] and k=2 groups, find the minimum possible maximum sum of a group (minimize the largest subarray sum).

Papers

Megiddo, N. — Applying Parallel Computation Algorithms in the Design of Serial Algorithms (1983, Journal of the ACM)

Blogs

Koko Eating Bananas — NeetCode Parametric Search — Wikipedia

A leaderboard holds a million sorted scores and you must answer, over and over, how many players scored at least 80, or where a new score of 80 should be inserted to keep the list sorted. The score 80 may appear many times or not at all, so a search that returns "found at some index" is not good enough. You need a precise position: the first slot whose value is at least 80.

The previous topic, Monotonic Function, taught that binary search really finds the boundary of a monotonic predicate. Applying that view to a sorted array with the predicate "arr[i] >= target" gives the lower bound, also known as bisect_left in Python or std::lower_bound in C++. It always returns a valid insertion point, handles duplicates without special cases, and never needs to test for equality.

We first build the lower-bound template and trace it on duplicates. Then we add its twin, the upper bound, the first element strictly greater than the target, and combine the two to count occurrences and answer range queries in O(log n), which is the backbone of sorted-data indexes.

Definition

The lower bound of a target in a sorted array is the smallest index i with arr[i] >= target, or n if no such index exists; it equals the leftmost insertion point that keeps the array sorted. The upper bound is the smallest index with arr[i] > target. Both are found by binary search in O(log n) comparisons.

In this topic

1Lower Bound Binary Search
2Upper Bound and Range Queries

1 of 2

Lower Bound Binary Search

The lower bound search finds the leftmost position where target could be inserted without breaking the sorted order. If the target exists in the array, it returns the index of its first occurrence. If it does not exist, it returns the index where it would be inserted. The key difference from standard binary search: when arr[mid] == target, we do NOT return immediately. Instead, we set hi = mid to keep searching leftward for an earlier occurrence.

Mathematical Intuition

$\text{lower\_bound}(a, t)$ returns the smallest index $i$ with $a[i] \ge t$ . It is the transition index of the predicate $P(i) = (a[i] \ge t)$ , which is monotone on a sorted array. Runtime is $\Theta(\log n)$ with $\lceil \log_2 (n+1) \rceil$ comparisons. This single primitive implements equality search, range counts, and insertion points.

Example:

Find the lower bound of 5 in [1, 3, 5, 5, 5, 8, 10].

2 of 2

Upper Bound and Range Queries

Lower bound alone cannot tell you where a run of equal values ends, and counting or slicing a range needs both ends. The upper bound is the first index whose value is strictly greater than the target. Its code is identical to lower bound except the predicate changes from arr[mid] >= target to arr[mid] > target. Together they bracket every copy: the target occupies indices lower_bound(t) through upper_bound(t) - 1, so its count is upper_bound(t) - lower_bound(t), with zero meaning absent. For a value range [a, b], the matching slice runs from lower_bound(a) to upper_bound(b). Python exposes these as bisect_left and bisect_right.

Mathematical Intuition

$\text{upper\_bound}(a, t)$ returns the smallest $i$ with $a[i] > t$ . Combined with $\text{lower\_bound}$ , the count of elements equal to $t$ is $\text{upper\_bound}(a,t) - \text{lower\_bound}(a,t)$ , and the count in $[lo, hi]$ is $\text{upper\_bound}(a,hi) - \text{lower\_bound}(a,lo)$ — all $O(\log n)$ .

Example:

Count how many times 5 appears in [1, 3, 5, 5, 5, 8, 10] using lower and upper bound.

Papers

Kraska, T. et al. — The Case for Learned Index Structures (2018, SIGMOD)

Blogs

std::lower_bound / std::upper_bound — cppreference Python bisect — Docs

A server log is sorted by timestamp, and an incident began at 12:03:07. You need the very first log line from that second, because later lines at the same timestamp are symptoms, not the cause. A plain binary search happily reports whichever matching line it hits first, which is usually somewhere in the middle of the run.

The previous topic, First Element Not Smaller, solved a close cousin with lower bound, which returns an insertion point even when the target is absent. First occurrence adds one extra rule: the target must actually exist, otherwise return -1. More importantly, it teaches the most common binary-search correction in interviews. When arr[mid] == target, you are not done; you have a candidate, and there may be an earlier match to its left.

We first write the "record and keep searching" version that remembers the best index seen so far while continuing leftward. Then we mirror it to find the last occurrence, and combine the two to get the full range and count of a value in O(log n), regardless of how many duplicates there are.

Definition

The first occurrence of a target in a sorted array is the smallest index i with arr[i] == target, or -1 if the target is absent; the last occurrence is the largest such index. Both are found by binary search that records each match as a candidate and keeps narrowing toward the desired side, in O(log n) time.

In this topic

1Searching Past a Match
2Last Occurrence Variant

1 of 2

Searching Past a Match

In standard binary search, finding arr[mid] == target means you are done. In first-occurrence search, finding a match means you have a candidate answer, but there might be an earlier one. The strategy: when arr[mid] == target, save mid as the current best answer and set hi = mid - 1 to continue searching the left half. The loop still runs with lo <= hi. After the loop, return the saved answer (or -1 if no match was found).

Mathematical Intuition

Naïve binary search returns some match. To find the first match, change the update rule: when $a[m] = t$ , set $r = m$ (don't stop) instead of returning. This keeps searching the left half. Correctness: the invariant 'the first occurrence, if any, lies in $[l, r]$ ' is preserved because any occurrence to the right of $m$ cannot be the first. Still $\Theta(\log n)$ .

Example:

Find the first occurrence of 5 in [1, 3, 5, 5, 5, 7, 9].

2 of 2

Last Occurrence Variant

Finding the last occurrence is the mirror image of the first, and together they give the full extent of a value. The template is identical except for the direction of travel after a match: when arr[mid] == target, save mid as the candidate and set lo = mid + 1 to keep searching right; the other branches stay unchanged. With first and last in hand, the value occupies indices [first, last] and its count is last - first + 1. The tempting shortcut, finding one match and walking outward, costs O(k) for k duplicates and degrades to O(n). Running two separate O(log n) searches is always safe.

Mathematical Intuition

Symmetrically, to find the last occurrence, on match set $l = m + 1$ and remember $m$ as the best-so-far. Equivalently, $\text{lastOcc}(a, t) = \text{upper\_bound}(a, t) - 1$ when that index still equals $t$ . Counting duplicates then takes two binary searches for $\Theta(\log n)$ time instead of a linear scan.

Example:

Find both the first and last occurrence of 3 in [1, 2, 3, 3, 3, 3, 4, 5].

Papers

Khuong, P.-V. & Morin, P. — Array Layouts for Comparison-Based Searching (2017, ACM JEA)

Blogs

Find First and Last Position — NeetCode Leftmost / Rightmost Binary Search — GeeksforGeeks

Your code needs the square root of 2 to ten decimal places, or the interest rate that makes a loan's payments exactly match a target, and no library function gives it directly. What you do have is a way to check any guess: square it, or simulate the payments, and see whether you went too high or too low.

The previous topic, First Occurrence, worked on discrete indices, where each step could skip past mid with mid + 1. Here the candidates are real numbers, so there is no next index to step to. Instead, we keep an interval [lo, hi] that brackets the answer and halve its width every step, stopping once it is narrower than the precision we need. Because $x^2$ increases with x, the too-high or too-low verdict at the midpoint tells us which half to keep. This is the bisection method.

We first adapt the loop to continuous space, with a new stopping rule and no plus-one updates. Then we compute exactly how many iterations a given precision costs, and see why a fixed iteration count is safer than an epsilon test in floating point.

Definition

Binary search on real numbers, also called the bisection method, finds a value x where a monotonic function crosses a threshold by repeatedly halving an interval [lo, hi] known to contain it. After k iterations the interval width is (hi - lo) / 2^k, so reaching precision epsilon takes about log2((hi - lo) / epsilon) iterations.

In this topic

1Binary Search on Real Numbers
2Iteration Count and Convergence

1 of 2

Binary Search on Real Numbers

When searching over real numbers, the loop condition changes from lo <= hi (discrete) to hi - lo > epsilon (continuous), where epsilon is the desired precision (e.g., 1e-9). At each step, mid = (lo + hi) / 2.0. If mid * mid < target, the square root is larger, so lo = mid. If mid * mid > target, the square root is smaller, so hi = mid. Note: we use lo = mid (not mid + 1) because there is no 'next' value in continuous space.

Mathematical Intuition

For $f: [a,b] \to \mathbb{R}$ continuous and monotone, bisection converges linearly: after $k$ iterations, the interval width is $(b-a)/2^k$ . To guarantee error $< \varepsilon$ , we need $k \ge \log_2 \frac{b-a}{\varepsilon}$ iterations — independent of any $n$ . For double precision ( $\varepsilon \approx 10^{-15}$ ) on $[0, 10^9]$ , this is only $\sim 80$ iterations.

Example:

Estimate sqrt(2) to 4 decimal places using binary search.

2 of 2

Iteration Count and Convergence

Before running a real-valued search, you can predict its cost exactly. Each iteration halves the interval, so after k steps its width is R / 2^k, where R = hi - lo is the starting range. Requiring width below epsilon gives $k = \lceil \log_2(R / \varepsilon) \rceil$ , logarithmic in both range and precision: [0, 10^9] at 10^-9 needs about 60 iterations. The failure mode is floating point. A double carries about 16 significant digits, so when epsilon is smaller than the gap between adjacent doubles near the answer, hi - lo > eps never becomes false and the loop spins forever. A fixed count such as 100 iterations always terminates.

Mathematical Intuition

Bisection's error after $k$ steps is $e_k \le (b-a) \cdot 2^{-k}$ , so convergence is linear with rate $1/2$ (one bit of precision per iteration). Newton's method achieves quadratic convergence $e_{k+1} = O(e_k^2)$ on smooth functions, but bisection's advantage is robustness: it never diverges if the initial bracket contains a root, making it the method of choice when you care about guarantees over speed.

Example:

How many iterations does binary search need to estimate sqrt(1000000) with precision 10^-10?

Papers

Goldberg, D. — What Every Computer Scientist Should Know About Floating-Point Arithmetic (1991, ACM Computing Surveys)

Blogs

Methods of Computing Square Roots — Wikipedia Bisection Method — Wikipedia

A circular log buffer stores events in time order, but writing wrapped around, so the array now reads [40, 50, 60, 10, 20, 30] and the oldest entry sits somewhere in the middle. You need its position quickly, without scanning the whole buffer. The array is no longer sorted, so it seems the tools of this chapter no longer apply.

The previous topic, Square Root Estimation, searched a smooth monotonic function. A rotated sorted array is not monotonic, but it is almost: it consists of two sorted runs, and the minimum sits exactly at the break between them. The key insight is that comparing the middle element with the rightmost element reveals which side of the break mid is on, which is again a yes/no predicate that flips exactly once. So binary search still finds the minimum in O(log n).

We first derive the rule for identifying the sorted half and see why comparing with arr[hi] rather than arr[lo] also handles an unrotated array. Then we add duplicates, which can make the comparison ambiguous and, in the worst case, force a linear-time fallback.

Definition

A rotated sorted array is a sorted array whose first k elements have been moved to the end, forming two ascending runs; the minimum sits at the start of the second run. With distinct values, binary search comparing arr[mid] against arr[hi] locates it in O(log n). With duplicates, the worst case degrades to O(n).

In this topic

1Identifying the Sorted Half
2Handling Duplicates

1 of 2

Identifying the Sorted Half

In a rotated sorted array, at least one half (left or right of mid) is always properly sorted. Compare arr[mid] with arr[hi]: if arr[mid] > arr[hi], the rotation point (minimum) is in the right half, so lo = mid + 1. If arr[mid] <= arr[hi], the right half is sorted and the minimum is either at mid or in the left half, so hi = mid. This comparison with arr[hi] (not arr[lo]) is essential because it correctly handles the case when the array is not rotated at all.

Mathematical Intuition

In a rotated sorted array, at every iteration at least one of $[l, m]$ and $[m, r]$ is fully sorted — recognisable by comparing endpoints: $a[l] \le a[m]$ means the left half is sorted. Once you know which half is sorted, you can decide in $O(1)$ whether the target lies there (using the sorted-half's endpoints) and recurse. This preserves the $O(\log n)$ bound despite the rotation.

Example:

Find the minimum in [4, 5, 6, 7, 0, 1, 2].

2 of 2

Handling Duplicates

When the array can contain duplicates, arr[mid] == arr[hi] creates ambiguity --- you cannot determine which half to search. The solution is to shrink hi by 1: hi -= 1. This safely eliminates one element (since arr[mid] has the same value) without missing the minimum. However, this worst-case scenario (e.g., [1, 1, 1, 1, 0, 1, 1]) degrades the time complexity from O(log n) to O(n), because you might only eliminate one element per iteration.

Mathematical Intuition

With duplicates, $a[l] = a[m]$ no longer tells you which half is sorted — e.g., $[3, 3, 3, 1, 3]$ defeats the standard argument. The fix is to shrink the range: when $a[l] = a[m] = a[r]$ , increment $l$ (or decrement $r$ ). This degrades worst-case complexity to $\Theta(n)$ — e.g., an all-equal array with one different value — but remains $\Theta(\log n)$ on average.

Example:

Find the minimum in [2, 2, 2, 0, 1, 2] (array with duplicates).

Blogs

Find Minimum in Rotated Sorted Array — NeetCode Search in Rotated Sorted Array — NeetCode

Definition

A mountain array strictly increases up to a single peak index p and strictly decreases after it. Finding p is a binary search on the predicate arr[i] > arr[i + 1], which is False before p and True from p onwards. More generally, in any array with no equal neighbours, the same search returns some local peak in O(log n).

In this topic

1Using the Slope to Search
2Plateau and Multiple Peaks

1 of 2

Using the Slope to Search

At any index mid, compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], you are on the ascending slope --- the peak is to the right, so lo = mid + 1. If arr[mid] > arr[mid + 1], you are on the descending slope --- the peak is at mid or to the left, so hi = mid. The loop runs with while lo < hi and converges to the peak index when lo == hi.

Mathematical Intuition

In a mountain (unimodal) array, the peak is the unique index where $a[i] > a[i+1]$ . At each midpoint $m$ , the local slope $a[m+1] - a[m]$ tells you which side the peak is on: positive slope ⇒ peak in $(m, r]$ , negative slope ⇒ peak in $[l, m]$ . This reduces the range by half each iteration, giving $\Theta(\log n)$ . The invariant is 'a peak always lies in $[l, r]$ ', provable by induction using the endpoint conditions.

Example:

Find the peak in [1, 3, 5, 8, 6, 4, 2].

2 of 2

Plateau and Multiple Peaks

The slope rule relies on arr[mid] and arr[mid + 1] differing. On a plateau, where they are equal, the comparison says nothing about where the peak lies, and moving either way can skip it: in [1, 2, 2, 2, 2, 3, 1], choosing the left side when equal ends on a flat 2 and misses the peak 3 at index 5. Binary search is therefore only guaranteed when adjacent elements differ, which is why the classic Find Peak Element problem forbids equal neighbours; with plateaus, the safe fallback is an O(n) scan. With multiple strict local peaks, the search returns some local peak, not necessarily the global maximum.

Mathematical Intuition

If equal values form plateaus, the slope test $a[m+1] = a[m]$ is uninformative and you must scan past the plateau — worst case $\Theta(n)$ when the whole array is constant. For the Find Peak Element problem where $a[i] \ne a[i+1]$ is guaranteed, the slope test is always decisive and $\Theta(\log n)$ is restored. Multiple peaks are fine — binary search finds any one of them.

Example:

Find a peak in [1, 3, 5, 5, 4, 2] where there is a plateau at indices 2 and 3.

Papers

Kiefer, J. — Sequential Minimax Search for a Maximum (1953, Proceedings of the AMS)

Blogs

Find Peak Element — NeetCode Unimodal Function — Wikipedia

Vanilla Binary Search

Sorted Boolean Pattern

Binary Search on Answer

Lower / Upper Bound

First / Last Occurrence

Binary Search on Reals

Rotated Arrays

Peaks and Slopes

8 topics in this chapter

Vanilla Binary Search

Definition

In this topic

The Halving Principle

Implementation Details and Edge Cases

Related Problems on PixelBank

Sorted Boolean Array

Definition

In this topic

The Monotonic Boolean Pattern

Handling Edge Cases

Related Problems on PixelBank

Monotonic Function

Definition

In this topic

Binary Search on Answer Space

Designing the Feasibility Check

First Element Not Smaller

Definition

In this topic

Lower Bound Binary Search

Upper Bound and Range Queries

First Occurrence

Definition

In this topic

Searching Past a Match

Last Occurrence Variant

Square Root Estimation

Definition

In this topic

Binary Search on Real Numbers

Iteration Count and Convergence

Minimum in Rotated Array

Definition

In this topic

Identifying the Sorted Half

Handling Duplicates

Related Problems on PixelBank

Peak of Mountain Array

Definition

In this topic

Using the Slope to Search

Plateau and Multiple Peaks

Related Problems on PixelBank