What must I do before binary_search?

The range must be sorted according to the same comparison (non-decreasing by default). On unsorted data, behavior is undefined.

lower_bound vs upper_bound?

lower_bound finds the first position where value <= *it in the weak ordering sense (first not less than value); upper_bound finds the first strictly greater.

When is equal_range convenient?

When equal keys are contiguous and you want both ends of the run in one call.

C++ Search Algorithms: find, binary_search, lower_bound & equal_range

Q: find vs binary_search?

Small or unsorted data: find is simple. Large sorted arrays: binary search family is O(log n).

Q: When is equal_range convenient?

When equal keys are contiguous and you want both ends of the run in one call.

2026년 3월 12일 · 10분 읽기 · 수정 2026년 3월 12일 Intermediate tutorial

이 글의 핵심

STL search operations: linear vs binary, sorted preconditions, and iterator safety.

What are search algorithms?

They locate values or predicates in ranges: linear find / find_if, or binary search algorithms on sorted ranges.

Search family overview

Algorithm	Time	Sorted?	Role
`find`	O(n)	No	First equal value
`find_if`	O(n)	No	First pred true
`binary_search`	O(log n)	Yes	Existence
`lower_bound`	O(log n)	Yes	First not-before value
`upper_bound`	O(log n)	Yes	First after value
`equal_range`	O(log n)	Yes	Subrange of equal keys

flowchart TD
    A["Start search"]
    B{"Sorted?"}
    C{"Value search?"}
    D["find"]
    E["find_if"]
    F{"Existence only?"}
    G["binary_search"]
    H{"Need position?"}
    I["lower_bound"]
    J["equal_range"]
    
    A --> B
    B -->|No| C
    C -->|Yes| D
    C -->|No| E
    B -->|Yes| F
    F -->|Yes| G
    F -->|No| H
    H -->|Yes| I
    H -->|No| J

find / find_if

Linear scan; no sort required.

binary_search, lower_bound, upper_bound, equal_range

Must sort first (or maintain sorted order). binary_search returns bool; use lower_bound when you need an iterator.

Common pitfalls

Unsorted + binary: undefined behavior.
Iterator invalidation after vector::insert / push_back — store index or redo search.
Repeated searches: sort once, then many O(log n) queries.

Production patterns

Conditional find_if (e.g. active user by name), range between bounds with lower_bound/upper_bound, insertSorted with lower_bound + insert.

FAQ

Full Q&A mirrors Korean article: find vs binary_search, lower vs upper, equal_range, UB on unsorted data, find_if O(n), iterator invalidation, resources (Effective STL, cppreference).

C++ Algorithm MinMax
C++ Algorithm Partition
C++ Algorithm Guide

Keywords

std::find, binary_search, lower_bound, upper_bound, equal_range, STL, binary search