Binary Search — Use binary search conceptually (and std::binary_search) (intro) - C Plus Plus

SECTION 1

Historical Context & Motivation

The idea of searching by repeatedly halving a range is remarkably old, predating electronic computers by centuries. Long before anyone wrote a line of C++, mathematicians and librarians understood that looking up a word in a dictionary does not require scanning every page from A to Z — you open roughly to the middle, decide which half contains your target, and repeat. This intuitive strategy became one of the first algorithms to be formalized when digital computing emerged in the mid-twentieth century, yet getting all the edge cases correct proved surprisingly difficult. The history of binary search is a vivid reminder that even simple-sounding algorithms demand precision in implementation.

1946 • First Published Description

John Mauchly describes binary search in a lecture at the Moore School of Electrical Engineering, making it one of the earliest documented computer algorithms.

1960 • First Bug-Free Version

Derrick Henry Lehmer and others note that every published implementation contains subtle off-by-one or overflow bugs. A provably correct version is not published until 1962 by Hermann Bottenbruch.

1998 • C++ Standard Library Adoption

The C++98 standard formalizes std::binary_search, std::lower_bound, and std::upper_bound in the <algorithm> header, providing efficient, tested implementations for sorted ranges.

2006 • Java's Famous Bug

Joshua Bloch reveals that Java's Arrays.binarySearch contained an integer overflow bug that went unnoticed for nearly a decade, reinforcing how tricky correct implementation remains even for expert engineers.

The central question binary search addresses is deceptively simple: given a sorted collection of elements, how can we determine whether a particular value is present — and do so far more efficiently than inspecting every element one by one? As we will see, the answer leverages the sortedness invariant to discard half the remaining search space at each step, yielding logarithmic time complexity.

SECTION 2

Core Principles & Definitions

Binary search rests on a small number of elegant principles that, taken together, guarantee both correctness and efficiency. Understanding these principles conceptually is essential before examining any code, because every line in a binary search implementation exists to preserve one of these invariants.

Sorted Precondition

Binary search requires the input to be sorted with respect to the comparison criterion. If the range is not sorted, the algorithm's branching decisions become meaningless, and the result is undefined behavior when using std::binary_search.

Divide and Conquer

At each iteration, the algorithm computes the midpoint of the current range, compares the target to the midpoint element, and eliminates exactly one half of the range. This halving strategy is a canonical example of divide-and-conquer.

Loop Invariant

A correct binary search maintains the invariant that, if the target exists in the original range, it must lie within the current subrange [low, high). This invariant holds at entry, is preserved by each iteration, and upon termination tells us the answer.

Logarithmic Convergence

Because the search space halves each step, at most ⌈log₂(n)⌉ comparisons are needed. For a billion elements, this is roughly 30 comparisons — an astronomically better bound than the n comparisons required by linear search.

Boolean Return vs. Iterator Return

std::binary_search returns true or false (existence query). When you need the position, use std::lower_bound or std::upper_bound instead.

✦

KEY TAKEAWAY

Think of binary search like a number-guessing game in which you are told "higher" or "lower" after each guess. If you always guess the midpoint of the remaining range, you are guaranteed to find the number (or prove it doesn't exist) in at most ⌈log₂(n)⌉ guesses. This is the same strategy a doctor uses when performing a bisection to narrow down a patient's threshold dose: test the middle value, discard half the interval, and repeat.

SECTION 3

Visual Explanation — Binary Search Step by Step

The following diagram traces a binary search for the value 23 within a sorted array of eight elements. Each row represents one iteration: the gray region has been eliminated, the highlighted region is the active subrange, and the arrow points to the midpoint element being compared.

Each pass halves the active range (highlighted in cyan). The yellow arrow marks the midpoint being compared. By pass 3, the range has collapsed to a single element that matches the target, and the search terminates successfully after only 3 comparisons.

Notice how the eliminated regions (shown with reduced opacity) grow with each pass. After only three iterations, seven of the eight elements have been discarded and the target is identified. Had we searched linearly from the beginning, we would have inspected five elements before reaching 23 at index 4. For small arrays the savings are modest, but for a million elements the difference between ~20 comparisons (binary) and ~500,000 comparisons (linear, on average) is transformative.

SECTION 4

Mathematical Framework

The efficiency of binary search follows directly from the geometric rate at which the search space shrinks. Let n denote the number of elements in the sorted range and T(n) the number of comparisons required in the worst case. At each step we make one comparison and reduce the problem to a subproblem of size at most ⌊n/2⌋, giving the recurrence relation below.

RECURRENCE RELATION

T(n) = T(⌊n/2⌋) + 1, T(1) = 1

T(n) = worst-case comparisons for n elements. The +1 accounts for the single comparison at the midpoint. The base case T(1) = 1 means checking one element costs one comparison.

CLOSED-FORM SOLUTION

T(n) = ⌈log₂(n)⌉ + 1 ∈ O(log n)

Solving the recurrence by unrolling: after k halvings the range has size n/2ᵏ. We stop when n/2ᵏ ≤ 1, i.e., k = ⌈log₂(n)⌉. Each halving costs one comparison, and we may need one final comparison, giving the expression above.

MIDPOINT CALCULATION (OVERFLOW-SAFE)

mid = low + (high − low) / 2

Computing the midpoint as (low + high) / 2 can overflow if low + high exceeds the maximum integer value. The equivalent formula low + (high − low) / 2 avoids this pitfall — the subtraction high − low is always non-negative and bounded by n.

It is worth noting that O(log n) comparisons represents the information-theoretic lower bound for comparison-based searching in a sorted array: any algorithm that distinguishes among n possible positions must make at least ⌈log₂(n)⌉ binary decisions. Binary search therefore achieves optimal worst-case comparison count among deterministic comparison-based algorithms. The space complexity is O(1) for the iterative formulation, since only a constant number of index variables are maintained regardless of n.

SECTION 5

The std::binary_search Family in C++

The C++ Standard Library provides three closely related functions in the <algorithm> header that all rely on binary search internally. Understanding when to use each is essential for writing idiomatic C++ and avoiding the common mistake of writing a hand-rolled binary search when a standard facility already exists.

The three functions in the binary search family serve different purposes. std::binary_search answers an existence question. std::lower_bound finds the first position where the value could be inserted without breaking sorted order. std::upper_bound finds the position just past the last equivalent element. The difference between the two iterators gives the count of matching elements.

Function	Signature (simplified)	Returns	Complexity
`std::binary_search`	`binary_search(first, last, value)`	`bool`	O(log n) for random-access iterators
`std::lower_bound`	`lower_bound(first, last, value)`	Iterator to first element ≥ value	O(log n) for random-access iterators
`std::upper_bound`	`upper_bound(first, last, value)`	Iterator to first element > value	O(log n) for random-access iterators

All three functions accept an optional fourth argument: a comparison functor or lambda for custom ordering.

⚠

IMPORTANT

All three functions have a precondition that the range [first, last) must be partitioned with respect to the comparison criterion (which is satisfied whenever the range is fully sorted). Calling them on an unsorted range is undefined behavior — the compiler will not warn you, and the result may appear correct for some inputs while silently producing wrong answers for others.

SECTION 6

Worked Example — Using std::binary_search

Consider a problem in which you are given a sorted vector of student IDs and must determine whether a particular ID exists in the roster. We will solve this using std::binary_search and then extend the solution to find the position using std::lower_bound.

Finding a Student ID in a Sorted Roster

1
Step 1 — Set Up the Sorted Data

We have a sorted vector: std::vector<int> roster = {1001, 1034, 1078, 1120, 1245, 1300, 1455, 1589}; and we want to check whether student ID 1245 is enrolled. The vector contains n = 8 elements and is sorted in ascending order, satisfying the precondition for binary search.
2
Step 2 — Call std::binary_search

We write: bool found = std::binary_search(roster.begin(), roster.end(), 1245); Internally, the function computes mid indices and compares. The half-open range is [0, 8), so mid = 0 + (8 − 0)/2 = 4. The element at index 4 is 1245, which equals our target.

found = true — determined in a single comparison (best case).
3
Step 3 — Find the Position with std::lower_bound

Since std::binary_search only returns a bool, we use std::lower_bound when we also need the iterator: auto it = std::lower_bound(roster.begin(), roster.end(), 1245); We then verify: if (it != roster.end() && *it == 1245) — the two-part check ensures both that the iterator is valid and that it actually points to our target (since lower_bound may point to the next larger element if the target is absent).

it points to index 4, and *it == 1245. Position confirmed.
4
Step 4 — Analyze Complexity

For n = 8, the worst case is ⌈log₂(8)⌉ = 3 comparisons. We hit the best case here (1 comparison) because the target happened to be at the midpoint. If we had searched for 1589 (the last element), the algorithm would have needed all 3 passes. Regardless, the time complexity is O(log n) and the space complexity is O(1).

Worst-case comparisons: ⌈log₂(8)⌉ = 3. Actual comparisons: 1.

SECTION 7

Binary Search vs. Linear Search — Strengths & Limitations

Binary search is not universally superior to linear search — each has a proper domain. The following table summarizes the trade-offs that should guide your algorithm selection.

Criterion	Linear Search	Binary Search
Time complexity	O(n) worst and average case	O(log n) worst and average case
Precondition	None — works on unsorted data	Data must be sorted (or partitioned)
Data structure	Any iterable (list, stream, etc.)	Random-access container for O(log n); forward iterators degrade to O(n)
Space	O(1)	O(1) iterative; O(log n) recursive stack
Sorting cost	Not applicable	O(n log n) if data is not already sorted — amortized over many queries
Best for	Small or unsorted collections; one-time lookups	Large sorted collections; repeated lookups

Choose binary search when the data is already sorted or when sorting cost is amortized across many queries.

✦

KEY TAKEAWAY

Binary search trades a one-time O(n log n) sorting cost for O(log n) per query, whereas linear search costs O(n) per query but requires no preprocessing. If you will perform Q queries on a static dataset of size n, binary search wins when Q × log n + n log n < Q × n — which is true even for modest Q. This is analogous to building an index for a library: the upfront effort of organizing the catalog pays for itself after just a few patron lookups.

SECTION 8

Connection to Advanced Techniques

The binary search pattern extends well beyond simple array lookups. Once you internalize the idea of halving a search space based on a monotonic predicate, you will recognize opportunities to apply the same technique to continuous domains (bisection method for root-finding), answer-space problems in competitive programming (binary search on the answer), and data structures like balanced BSTs and B-trees that generalize the concept to dynamic data.

Introductory Concept	Advanced Extension
`std::binary_search` on a sorted vector	Binary search on a monotonic predicate ("binary search the answer")
Integer midpoint: low + (high − low) / 2	Floating-point bisection: iterate until \|high − low\| < ε for numerical root-finding
Searching a static sorted array	Self-balancing BSTs (AVL, Red-Black) and B-trees for dynamic sorted data with O(log n) insert/search
`std::lower_bound` / `std::upper_bound`	`std::equal_range` which returns both bounds in a single call, and custom comparator overloads for non-trivial orderings

A particularly powerful generalization is binary search on the answer: given an optimization problem where you can efficiently check "is a solution of quality ≥ k feasible?" and the answer is monotonic in k, you can binary search over k to find the optimal solution in O(log(range) × cost_of_check). This technique appears frequently in competitive programming, operations research, and numerical analysis. Mastering the introductory version presented in this lesson is the prerequisite for all these extensions.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why binary search requires the input to be sorted. What would go wrong if you called std::binary_search on the unsorted array {5, 2, 8, 1, 9} looking for the value 8?

Show answer

Binary search relies on the invariant that comparing the target to the midpoint element tells us which half of the range to eliminate. In a sorted array, all elements to the left of the midpoint are smaller and all to the right are larger (for ascending order). In the unsorted array {5, 2, 8, 1, 9}, the midpoint element is 8 (index 2). The algorithm might conclude the target is found (lucky hit), but if you searched for 2, the midpoint comparison 2 < 8 would direct the search to the left subarray {5, 2}, then mid = 5, and 2 < 5 would direct it to {}, producing a false negative. The C++ standard explicitly states this is undefined behavior — the result is unpredictable.

Question 2: BASIC CALCULATION

A sorted array has 1,000,000 elements. What is the maximum number of comparisons binary search will perform? Compare this to the average number of comparisons for linear search.

Show answer

The maximum number of comparisons for binary search is ⌈log₂(1,000,000)⌉ = ⌈19.93⌉ = 20. Linear search on average examines n/2 = 500,000 elements (assuming the target is present and equally likely to be at any position). Binary search is therefore roughly 25,000 times faster in terms of comparisons. Even in the worst case (target absent), linear search checks all 1,000,000 elements, while binary search still needs only 20 comparisons. This dramatic gap illustrates why O(log n) is qualitatively different from O(n) for large datasets.

Question 3: INTERMEDIATE

Given the sorted vector {10, 20, 20, 20, 30, 40, 50}, write C++ code using std::lower_bound and std::upper_bound to count how many times the value 20 appears. What indices do the returned iterators point to?

Show answer

The code is:

auto lo = std::lower_bound(v.begin(), v.end(), 20); auto hi = std::upper_bound(v.begin(), v.end(), 20); int count = hi - lo;

Here, lower_bound returns an iterator to index 1 (the first 20), and upper_bound returns an iterator to index 4 (the element 30, which is the first element strictly greater than 20). The count is 4 − 1 = 3. Alternatively, std::equal_range(v.begin(), v.end(), 20) returns both iterators as a pair in a single call with the same O(log n) complexity.

Question 4: APPLIED

You are building a spell-checker that stores a dictionary of 200,000 words in a sorted std::vector<std::string>. For each word in a user's document (average 500 words), you need to check if it exists in the dictionary. Compare the total cost of (a) using linear search for each word, and (b) using std::binary_search for each word. Assume string comparisons cost O(1) for simplicity.

Show answer

With linear search, each lookup costs O(n) = O(200,000) in the worst case, so checking 500 words costs 500 × 200,000 = 100,000,000 comparisons. With binary search, each lookup costs O(log₂ 200,000) ≈ O(18) comparisons, so checking 500 words costs 500 × 18 = 9,000 comparisons — over 11,000 times fewer. The dictionary is already sorted (alphabetical order), so no sorting cost is incurred. Even if sorting were needed, its O(n log n) = 200,000 × 18 ≈ 3,600,000 cost is trivially amortized. This scenario perfectly illustrates why binary search dominates for repeated queries on static sorted data.

Question 5: CRITICAL THINKING

The standard std::binary_search uses the concept of equivalence rather than equality: two elements a and b are considered equivalent if !(a < b) && !(b < a). Construct an example using a custom comparator where two objects are "equivalent" under this definition but are not "equal" in the intuitive sense. Why does the C++ standard use equivalence instead of equality?

Show answer

Consider a struct Student { string name; double gpa; } sorted by GPA using a comparator auto cmp = [](const Student& a, const Student& b) { return a.gpa < b.gpa; }. Two students Alice (GPA 3.5) and Bob (GPA 3.5) satisfy !(Alice < Bob) && !(Bob < Alice) — they are equivalent under the comparator — but they are clearly not equal objects (different names). If you call std::binary_search(v.begin(), v.end(), Student{"Charlie", 3.5}, cmp), it returns true because an equivalent element exists, even though "Charlie" may not be in the vector. The C++ standard uses equivalence rather than equality because the library's sorted-range algorithms are parameterized only by a strict weak ordering (operator< or a comparator), and equivalence is the natural notion that arises from an ordering. Requiring equality would force the library to demand operator== as well, coupling two independent concepts and reducing generality.

SUMMARY

Lesson Summary

Summary

Binary search is a divide-and-conquer algorithm that locates a target value within a sorted range by repeatedly comparing the target to the midpoint element and discarding half the search space. Its O(log n) time complexity is information-theoretically optimal for comparison-based searching, requiring at most ⌈log₂(n)⌉ comparisons — roughly 20 for a million elements and 30 for a billion. The critical precondition is that the input must be sorted; calling binary search on unsorted data is undefined behavior.

In C++, the Standard Library provides std::binary_search for existence queries (returns bool), std::lower_bound for finding the first position of a value, and std::upper_bound for finding the position just past the last equivalent element. The correct midpoint formula is mid = low + (high − low) / 2 to avoid integer overflow. Binary search trades an upfront sorting cost of O(n log n) for dramatically faster per-query performance, making it the clear choice when multiple lookups are performed on static or infrequently changing data.