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

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

· 24분 읽기 · 수정 Intermediate tutorial
C++ Search Algorithms: find, binary_search, lower_bound &

이 글의 핵심

Choose between linear find and binary search on sorted ranges; use lower_bound, upper_bound, and equal_range for positions and equal-key runs in C++.

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

AlgorithmTimeSorted?Role
findO(n)NoFirst equal value
find_ifO(n)NoFirst pred true
binary_searchO(log n)YesExistence
lower_boundO(log n)YesFirst not-before value
upper_boundO(log n)YesFirst after value
equal_rangeO(log n)YesSubrange of equal keys

std::find and std::find_if

Basic find

#include <algorithm>
#include <vector>
#include <iostream>
std::vector<int> numbers = {1, 3, 5, 7, 9, 11};
// Find specific value
auto it = std::find(numbers.begin(), numbers.end(), 7);
if (it != numbers.end()) {
    std::cout << "Found: " << *it << " at index " 
              << std::distance(numbers.begin(), it) << "\n";
} else {
    std::cout << "Not found\n";
}

find_if with predicate

#include <algorithm>
#include <vector>
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
// Find first even number
auto it = std::find_if(numbers.begin(), numbers.end(),
                       [](int x) { return x % 2 == 0; });
if (it != numbers.end()) {
    std::cout << "First even: " << *it << "\n";  // 2
}

find_if_not

// Find first NOT matching predicate
auto it = std::find_if_not(numbers.begin(), numbers.end(),
                           [](int x) { return x < 5; });
// Finds first element >= 5

Binary search algorithms

Critical: Range must be sorted first!

Returns bool indicating existence:

#include <algorithm>
#include <vector>
std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};
bool found = std::binary_search(sorted.begin(), sorted.end(), 7);
// true
bool notFound = std::binary_search(sorted.begin(), sorted.end(), 6);
// false

std::lower_bound

Finds first position where element could be inserted maintaining order:

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto it = std::lower_bound(sorted.begin(), sorted.end(), 5);
// Points to first 5
std::cout << "Index: " << std::distance(sorted.begin(), it) << "\n";  // 2
std::cout << "Value: " << *it << "\n";  // 5
// For value not present
auto it2 = std::lower_bound(sorted.begin(), sorted.end(), 6);
// Points to 7 (first element >= 6)

std::upper_bound

Finds first position strictly greater than value:

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto it = std::upper_bound(sorted.begin(), sorted.end(), 5);
// Points to 7 (first element > 5)
std::cout << "Index: " << std::distance(sorted.begin(), it) << "\n";  // 5
std::cout << "Value: " << *it << "\n";  // 7

std::equal_range

Returns pair of iterators [lower_bound, upper_bound):

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
auto [first, last] = std::equal_range(sorted.begin(), sorted.end(), 5);
std::cout << "Count of 5: " << std::distance(first, last) << "\n";  // 3
// Print all occurrences
for (auto it = first; it != last; ++it) {
    std::cout << *it << " ";
}
// Output: 5 5 5

Real-world examples

1. User search by ID

#include <algorithm>
#include <vector>
#include <string>
struct User {
    int id;
    std::string name;
    
    bool operator<(const User& other) const {
        return id < other.id;
    }
};
std::vector<User> users = {
    {1, "Alice"},
    {3, "Bob"},
    {5, "Charlie"},
    {7, "David"}
};
// Must be sorted by id
std::sort(users.begin(), users.end());
// Binary search by id
User target{5, ""};
auto it = std::lower_bound(users.begin(), users.end(), target);
if (it != users.end() && it->id == 5) {
    std::cout << "Found: " << it->name << "\n";  // Charlie
}

2. Range query

#include <algorithm>
#include <vector>
std::vector<int> timestamps = {100, 150, 200, 250, 300, 350, 400};
// Find all events between 180 and 320
auto start = std::lower_bound(timestamps.begin(), timestamps.end(), 180);
auto end = std::upper_bound(timestamps.begin(), timestamps.end(), 320);
std::cout << "Events in range: ";
for (auto it = start; it != end; ++it) {
    std::cout << *it << " ";
}
// Output: 200 250 300

3. Insert maintaining sorted order

#include <algorithm>
#include <vector>
std::vector<int> sorted = {1, 3, 5, 7, 9};
int newValue = 6;
auto pos = std::lower_bound(sorted.begin(), sorted.end(), newValue);
sorted.insert(pos, newValue);
// sorted is now {1, 3, 5, 6, 7, 9}

4. Finding first/last occurrence

std::vector<int> data = {1, 2, 2, 2, 3, 4};
// First occurrence of 2
auto first = std::lower_bound(data.begin(), data.end(), 2);
// Last occurrence of 2
auto last = std::upper_bound(data.begin(), data.end(), 2);
--last;  // Move back to last 2
std::cout << "First 2 at index: " << std::distance(data.begin(), first) << "\n";  // 1
std::cout << "Last 2 at index: " << std::distance(data.begin(), last) << "\n";    // 3

Performance comparison

Benchmark (1M sorted elements, 10K searches):

AlgorithmTime (ms)Notes
std::find450Linear scan
std::binary_search2O(log n)
std::lower_bound2O(log n)
std::upper_bound2O(log n)
std::equal_range3Two binary searches
Key insight: Binary search is 225× faster for large sorted data.

Common mistakes

Mistake 1: Binary search on unsorted data

std::vector<int> unsorted = {5, 2, 8, 1, 9};
// ❌ Undefined behavior!
bool found = std::binary_search(unsorted.begin(), unsorted.end(), 5);
// ✅ Sort first
std::sort(unsorted.begin(), unsorted.end());
bool found = std::binary_search(unsorted.begin(), unsorted.end(), 5);

Mistake 2: Not checking iterator validity

std::vector<int> data = {1, 2, 3};
auto it = std::find(data.begin(), data.end(), 5);
// ❌ Dereferencing end()
std::cout << *it << "\n";  // Undefined behavior!
// ✅ Check first
if (it != data.end()) {
    std::cout << *it << "\n";
}

Mistake 3: Using wrong bound

std::vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
// Want to insert after all 5s
auto it = std::lower_bound(sorted.begin(), sorted.end(), 5);  // ❌ Wrong!
// This gives position of first 5
auto it = std::upper_bound(sorted.begin(), sorted.end(), 5);  // ✅ Correct
// This gives position after last 5

Mistake 4: Iterator invalidation

std::vector<int> data = {1, 2, 3, 4, 5};
auto it = std::find(data.begin(), data.end(), 3);
data.push_back(6);  // May reallocate!
// ❌ it may be invalid now
std::cout << *it << "\n";  // Undefined behavior
// ✅ Store index or re-search
size_t index = std::distance(data.begin(), it);
data.push_back(6);
std::cout << data[index] << "\n";

Advanced patterns

1. Custom comparator

#include <algorithm>
#include <vector>
#include <string>
struct Person {
    std::string name;
    int age;
};
std::vector<Person> people = {
    {"Alice", 25},
    {"Bob", 30},
    {"Charlie", 35}
};
// Sort by age
std::sort(people.begin(), people.end(),
         [](const Person& a, const Person& b) {
             return a.age < b.age;
         });
// Binary search by age (must use same comparator!)
Person target{"", 30};
auto it = std::lower_bound(people.begin(), people.end(), target,
                          [](const Person& a, const Person& b) {
                              return a.age < b.age;
                          });
if (it != people.end() && it->age == 30) {
    std::cout << "Found: " << it->name << "\n";  // Bob
}

2. Count occurrences in sorted range

std::vector<int> data = {1, 2, 2, 2, 3, 4, 4, 5};
int value = 2;
auto range = std::equal_range(data.begin(), data.end(), value);
size_t count = std::distance(range.first, range.second);
std::cout << "Count of " << value << ": " << count << "\n";  // 3

3. Closest element

std::vector<int> sorted = {10, 20, 30, 40, 50};
int target = 27;
auto it = std::lower_bound(sorted.begin(), sorted.end(), target);
// Check both it and it-1 for closest
int closest;
if (it == sorted.begin()) {
    closest = *it;
} else if (it == sorted.end()) {
    closest = *(it - 1);
} else {
    int before = *(it - 1);
    int after = *it;
    closest = (target - before < after - target) ? before : after;
}
std::cout << "Closest to " << target << ": " << closest << "\n";  // 30

Choosing the right algorithm

The following example demonstrates the concept in mermaid:

flowchart TD
    A[Need to search?]
    B{Data sorted?}
    C{Need position?}
    D[std::find]
    E{Existence only?}
    F[std::binary_search]
    G{Need range?}
    H[std::equal_range]
    I[std::lower_bound]
    
    A --> B
    B -->|No| C
    C -->|No| D
    C -->|Yes| D
    B -->|Yes| E
    E -->|Yes| F
    E -->|No| G
    G -->|Yes| H
    G -->|No| I

Compiler support

Compilerfind/find_ifBinary searchequal_range
GCCAll versionsAll versionsAll versions
ClangAll versionsAll versionsAll versions
MSVCAll versionsAll versionsAll versions

Keywords

std::find, binary_search, lower_bound, upper_bound, equal_range, STL, binary search, C++, algorithm, search

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Choose between linear find and binary search on sorted ranges; use lower_bound, upper_bound, and equal_range for positio…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence. See the C++ series index for the full picture.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers C++, Algorithm, search, find, STL.