Skip to content

Searching

1
std::vector v = {5, 4, 9, 8, 6, 3};

1
2
3
4
5
6
7
// - std::find is what you would use daily
// - don't implement your own version unless you're studying the algorithms
auto i1 = std::find(v.begin(), v.end(), 6);
if (i1 != v.end()) {
    std::cout << "*i1: " << *i1 << '\n';
}
std::cout << "position: " << i1 - v.begin() << '\n';

1
sort(v.begin(), v.end());

1
2
3
4
5
6
7
// - std::lower_bound is what you would use daily
// - don't implement your own version unless you're studying the algorithms
auto i2 = lower_bound(v.begin(), v.end(), 6);
if (i2 != v.end()) {
    std::cout << "*i2: " << *i2 << '\n';
}
std::cout << "position: " << i2 - v.begin() << '\n';

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// This is what you would probably learn in college
// Example only. Use std::find instead.
size_t sequential_find(const std::vector<int> &v, const int key) {
    for (size_t i = 0; i < v.size(); ++i) {
        if (v[i] == key) {
            return i;
        }
    }
    // return a sentinel
    return v.size();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// This is what works in C++ for most container types.
// Example only. Use std::find instead.
template <class It, class T>
constexpr It sequential_find(It first, It last, const T &value) {
    for (; first != last; ++first) {
        // Best: O(1)
        // Worst: O(n)
        // Average: O(n)
        if (*first == value) {
            return first;
        }
    }
    // return a sentinel
    return last;
}

1
2
3
4
5
size_t pos1 = sequential_find(v, 6);
if (pos1 != v.size()) {
    std::cout << "value: " << v[pos1] << '\n';
}
std::cout << "position: " << pos1 << '\n';

1
2
3
4
5
auto it1 = sequential_find(v.begin(), v.end(), 6);
if (it1 != v.end()) {
    std::cout << "*it1: " << *it1 << '\n';
}
std::cout << "position: " << it1 - v.begin() << '\n';

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// This is what you would probably learn in college
// Example only. Use std::lower_bound instead.
size_t binary_find(const std::vector<int> &v, const int key) {
    size_t left_idx = 0;
    size_t right_idx = v.size() - 1;
    size_t i;
    do {
        i = (left_idx + right_idx) / 2;
        if (v[i] < key) {
            left_idx = i + 1;
        } else {
            right_idx = i - 1;
        }
    } while (v[i] != key && left_idx <= right_idx);
    return v[i] == key ? i : v.size();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// This is what works in C++ for most container types.
// Example only. Use std::lower_bound instead.
template <class It, class T>
It binary_find(It first, It last, const T &value) {
    typename std::iterator_traits<It>::difference_type count, step;
    It it;
    count = std::distance(first, last);
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (*it < value) {
            first = ++it;
            count -= step + 1;
        } else {
            count = step;
        }
    }
    return first;
}

1
2
3
4
5
size_t pos2 = binary_find(v, 6);
if (pos2 != v.size()) {
    std::cout << "value: " << v[pos2] << '\n';
}
std::cout << "position: " << pos2 << '\n';

1
2
3
4
5
auto it2 = binary_find(v.begin(), v.end(), 6);
if (it2 != v.end()) {
    std::cout << "*it2: " << *it2 << '\n';
}
std::cout << "position: " << it2 - v.begin() << '\n';

Share Snippets