Move Fast

이진 탐색 알고리즘 (Binary Search Algorithm)

• 시간 복잡도: O(log2(N)), 범위의 크기 = N

• 이미 정렬된 상태에서 수행해야 하며, 비교자 함수를 별도로 지정할 수 있음.

• lower_bound 특정 값보다 크거나 같은 원소들 중 가장 작은 값(하한)의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                                 const T& value, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct PriceInfo { double price; };

int main() {
    const vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 8; ++i) {
        // Search for first element x such that i ≤ x
        auto lower = lower_bound(data.begin(), data.end(), i);

        cout << i << " ≤ ";
        lower != data.end()
            ? cout << *lower << " at index " << distance(data.begin(), lower)
            : cout << "[not found]";
        cout << endl;
    }

    vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {102.5}, {107.3} };
    for(double to_find: {102.5, 110.2}) {
        auto prc_info = lower_bound(prices.begin(), prices.end(), to_find,
                                    [](const PriceInfo& info, double value){
                                        return info.price < value;
                                    });
        prc_info != prices.end()
            ? cout << prc_info->price << " at index " << prc_info - prices.begin()
            : cout << to_find << " not found";
        cout << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
0 ≤ 1 at index 0
1 ≤ 1 at index 0
2 ≤ 2 at index 1
3 ≤ 4 at index 2
4 ≤ 4 at index 2
5 ≤ 5 at index 3
6 ≤ 6 at index 5
7 ≤ [not found]
102.5 at index 2
110.2 not found
 */

• upper_bound 특정 값보다 큰 원소들 중 가장 작은 값(상한)의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value,
                       Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value,
                                 Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct PriceInfo { double price; };

int main() {
    const vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 7; ++i) {
        // Search first element that is greater than i
        auto upper = upper_bound(data.begin(), data.end(), i);

        cout << i << " < ";
        upper != data.end()
            ? cout << *upper << " at index " << distance(data.begin(), upper)
            : cout << "not found";
        cout << endl;
    }

    vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {107.3}, {109.8} };
    for(double to_find: {102.5, 110.2}) {
        auto prc_info = upper_bound(prices.begin(), prices.end(), to_find,
                                    [](double value, const PriceInfo& info){
                                        return value < info.price;
                                    });
        prc_info != prices.end()
            ? cout << prc_info->price << " at index " << prc_info - prices.begin()
            : cout << to_find << " not found";
        cout << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
0 < 1 at index 0
1 < 2 at index 1
2 < 4 at index 2
3 < 4 at index 2
4 < 5 at index 3
5 < 6 at index 5
6 < not found
107.3 at index 3
110.2 not found
 */

• binary_search 범위 내 특정 값과 일치하는 원소의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value,
                              Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> haystack {1, 3, 4, 5, 9};
    vector<int> needles {1, 2, 3};

    for (auto needle : needles) {
        cout << "Searching for " << needle << endl;
        if (binary_search(haystack.begin(), haystack.end(), needle)) {
            cout << "Found " << needle << endl;
        } else {
            cout << "no dice!" << endl;
        }
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3
 */

• equal_range 범위 내 특정 값과 일치하는 원소들의 부분 범위([lower_bound, upper_bound)) 반환.

// until C++20
template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last,
                                            const T& value );

template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt,ForwardIt> 
    equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt> 
              equal_range( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt> 
              equal_range( ForwardIt first, ForwardIt last,
                           const T& value, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct S {
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator< ( const S& s ) const { return number < s.number; }
};

int main() {
    // note: not ordered, only partitioned w.r.t. S defined below
    vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };

    S value = {2, '?'};

    auto p = equal_range(vec.begin(), vec.end(), value);
    for ( auto i = p.first; i != p.second; ++i )
        cout << i->name << ' ';
    cout << endl;

    // heterogeneous comparison:
    struct Comp {
        bool operator() ( const S& s, int i ) const { return s.number < i; }
        bool operator() ( int i, const S& s ) const { return i < s.number; }
    };

    auto p2 = equal_range(vec.begin(),vec.end(), 2, Comp{});
    for ( auto i = p2.first; i != p2.second; ++i )
        cout << i->name << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
B C D
B C D
 */