The <algorithm> header provides two families of search functions: linear scans that work on any sequence, and binary searches that require a sorted range. Picking the wrong family is one of the common STL mistakes: calling std::binary_search on an unsorted vector compiles, runs, and returns wrong answers. This chapter walks through both families, the iterator categories they expect, the rules around custom comparators, and the classic "I need the position, not a yes/no answer" pitfall.

Linear search visits elements one at a time. It works on any input iterator and runs in O(n). It does not care about ordering, so it applies to a std::vector, a std::list, a std::deque, or even a stream. Binary search halves the search space at every step and runs in O(log n) on a random-access range, but it requires the range to be sorted with the same comparator passed in.

A subtlety hides in that table. The binary search family accepts a forward iterator like the one std::list provides, and it still does O(log n) comparisons, but it has to walk the list to advance the iterator, so the total work is O(n). The complexity guarantee is on comparisons, not on steps. Binary search on a non-random-access container loses most of its appeal.

The diagram is the decision tree in one picture: if the data is not sorted, use a linear algorithm; if it is, binary is almost always faster.

std::find(first, last, value) walks [first, last) and returns the iterator to the first element equal to value, or last if nothing matches. Equality is checked with operator==, so the element type needs a usable ==.

The "did we find it?" check is always a comparison against end(). Dereferencing the returned iterator before that check is undefined behaviour if the value was not found.

std::find works on any container that exposes iterators, including ones without random access.

std::find is O(n). Calling it inside a loop that runs k times on the same n elements costs O(n*k). For hot lookups, consider a std::unordered_set or std::unordered_map, which give O(1) average lookup.

std::find only matches by operator==. For richer conditions, std::find_if(first, last, predicate) runs through the range and returns the first element for which predicate(element) returns true. std::find_if_not is the mirror: it returns the first element where the predicate is false.

The predicate is anything callable that takes a single element and returns something convertible to bool. Lambdas are the usual choice. A function pointer or a functor works too, which matters when the same predicate gets reused across multiple call sites.

A common pattern: skip over a leading run of items that do not match a condition.

This is a one-line replacement for a hand-written loop with an index, a guard, and a break.

std::count(first, last, value) returns how many elements in the range compare equal to value. std::count_if(first, last, predicate) counts how many satisfy the predicate. The return type is the iterator's difference_type, which is typically a signed integer wide enough to hold the size of the container.

count_if is the readable alternative to a loop that increments a counter on a condition. When the condition is non-trivial, it is also the alternative that is hard to get subtly wrong.

Both count and count_if are O(n) and always walk the entire range. There is no early exit at "seen enough"; for "is there at least one?", use any_of instead, which can stop early.

These three are the readable, intent-revealing way to ask quantifier questions over a range. Each returns a bool and short-circuits on the first conclusive answer.

By convention, all_of on an empty range returns true (vacuous truth) and any_of on an empty range returns false. none_of on an empty range returns true for the same reason as all_of.

These defaults are usually what is wanted, but they can surprise. "Are all items shipped?" answering true for an empty cart can be a bug if the cart was supposed to be non-empty.

std::find_first_of(first1, last1, first2, last2) returns the first iterator in [first1, last1) that matches any element in [first2, last2). It is an O(n*m) scan: for each element of the first range, it checks against every element of the second.

It returns the first match in the search range, not the first match in the sale set. If Notebook had been on sale, it would have been found earlier in the customer's cart and returned instead.

std::adjacent_find(first, last) returns an iterator to the first pair of consecutive equal elements, or last if no such pair exists. It detects runs of duplicates without writing the index arithmetic by hand.

adjacent_find only finds consecutive duplicates. To find any duplicate anywhere in the range, sort first then call adjacent_find, or use a set-based approach.

std::search(first1, last1, first2, last2) looks for the first occurrence of the subsequence [first2, last2) inside [first1, last1). It returns the iterator to the start of the match, or last1 if no match exists.

The naive worst case is O(n*m), where n is the haystack and m is the needle. For non-pathological inputs it is much faster.

std::search_n(first, last, count, value) looks for count consecutive copies of value. It fits when there is no separate needle range and the question is "is there a run of k matches?".

search_n answers "did stock stay at zero for at least three readings in a row?" without writing a state machine.

std::equal(first1, last1, first2) returns true if the two ranges have the same length and the same elements, in order. The two-iterator overload assumes the second range is at least as long as the first; for safety, use the four-iterator overload (C++14 and later) that takes both ends.

std::mismatch is the diagnostic version: it returns a std::pair of iterators pointing to the first position where the two ranges differ. If they are identical up to the end of the shorter range, both iterators point to the respective end().

mismatch writes a diff-friendly error message ("cart changed at position 2") rather than a yes/no answer.

Every algorithm so far has been O(n). When the data is sorted, better is possible. The binary search family answers the same kinds of questions in O(log n) comparisons by halving the search interval on every step.

A catch hides in the function names. The binary search family is sensitive to the order the data is in. Sorting one way and searching another way produces undefined behavior. The "comparator used to search" must match the "comparator used to sort" exactly. std::sort(v.begin(), v.end()) with the default < pairs with std::lower_bound(v.begin(), v.end(), x), also defaulting to <. Passing a custom comparator to sort requires passing the same comparator to the search.

That is binary search in one diagram: pick a midpoint, compare, throw away half the range, repeat. Doing this log_2 n times converges to either the value or a "not found" answer.

std::binary_search(first, last, value) returns true if value exists in the sorted range, false otherwise. It does not report where the value is. That is the common point of confusion for new STL users.

For a simple membership test, binary_search is the clearest answer. The moment the position, the discounted price, the stock count, or any other associated data is needed, switch to lower_bound.

binary_search is O(log n) comparisons on random-access iterators. On non-random-access iterators (like std::list), it still does O(log n) comparisons but O(n) steps to advance the iterator, so the total is O(n). Do not use binary search on linked lists; it also loses to a linear scan in cache behaviour.

These three are where binary search becomes broadly useful.

The names take a minute to learn. A useful model: lower_bound returns where v would be inserted to keep the range sorted; if v is already present, the iterator points to the first copy. upper_bound returns where it would be inserted after any existing equal copies.

The range [lower_bound, upper_bound) is the contiguous block of elements equal to the search value. Subtracting the iterators gives the count in O(1) after O(log n) on the bounds.

std::equal_range returns both endpoints in one call as a std::pair. Use it when both bounds are needed, instead of calling lower_bound and upper_bound back to back.

lower_bound also fits "find the first element at least as large as X." That is useful more often than equality testing.

There is no element equal to 50.0 in the range, and lower_bound does not need one. It returns the first element that is not less than 50.0, which is 79.99. That is the natural answer for "show me products at or above this price."

The task: know whether a product id exists in the catalog and print its discounted price. The natural first attempt:

binary_search reports "yes" but does not give the position. Anything more than a yes/no print requires a second search to recover the iterator. That is wasteful, and a sign of the wrong tool.

The idiomatic pattern is lower_bound plus a manual check for equality.

The two checks it != end() and *it == target are both required. lower_bound does not promise the element it points to is equal to the target; it promises it is the first not-less-than element. If target is bigger than every element, lower_bound returns end(), which must not be dereferenced.

This idiom is common enough that whenever std::binary_search is tempting, ask whether the position will be needed later. If yes, skip binary_search and go straight to lower_bound.

All the binary search functions accept an optional comparator as the last argument. The contract: the comparator must be a strict weak ordering, and the range must already be sorted by the same comparator. Passing one and forgetting the other produces nonsense answers, sometimes intermittently.

std::greater<int>{} is a functor that returns a > b. Sorting with greater produces descending order; searching with greater walks the data correctly. Sorting descending but searching with the default less makes the algorithm probe the wrong halves and produce undefined behaviour, not a clear failure.

For collections of custom types, the comparator usually compares one field.

Two things to note. First, the probe is a full Product even though only price matters; the comparator decides which field to compare. Second, the comparator must be the same one used at sort time. A subtle bug source: someone resorts the catalog by name later, the search code keeps using the price-based comparator, and the binary search returns wrong results without warning.

The standard says the behaviour of binary_search, lower_bound, upper_bound, and equal_range is undefined if the range is not sorted by the comparator passed. Undefined here means: any answer is allowed, and the compiler does not have to report the problem. The result is usually a wrong answer, not a crash.

On a typical g++ build this prints 0 even though 318 is in the vector. The function is not "broken"; it correctly applied the binary search algorithm, which assumed a sorted range and made wrong decisions about which half to discard. The fix is to sort the range first, or use a linear std::find if sorting is not worth the cost.

A defensive practice some teams adopt: assert std::is_sorted(first, last, cmp) in debug builds before calling a binary search function. It is an O(n) check, but only in debug, and it catches an entire class of bugs that otherwise go unreported.

The assert is cheap insurance. In release builds it compiles to nothing.

A small program that ties the chapter together. It maintains a catalog sorted by product id, supports both an exact lookup (by id) and a price-floor lookup (first product at or above some price), and uses linear search for an attribute that is not indexed (product name).

(The output shows the relevant lines; the actual program prints them in the order the code runs.) The takeaway: pick the algorithm that matches both the question and the data layout. An indexed sorted range supports binary search; an unindexed scan needs linear find. Mixing them, like calling binary_search against a range sorted by a different key, is the source of most search-related bugs.