C++로 정렬된 pair 벡터에서 이진 탐색 구현하기

이 글에서는 C++를 사용하여 정렬된 pair 벡터에서 이진 탐색(Binary Search)을 구현하는 방법을 단계별로 살펴봅니다.

핵심 개념

이진 탐색은 정렬된 자료구조에서 원하는 값을 O(log n)의 시간 복잡도로 빠르게 찾는 알고리즘입니다. C++ 표준 라이브러리(STL)는 <algorithm> 헤더의 binary_search() 함수를 제공하며, 이 함수는 탐색 범위와 찾으려는 값, 그리고 선택적으로 비교 기준을 인자로 받습니다.

pair<int, int>처럼 두 개의 값을 담는 요소를 다룰 때는 일반적으로 first(첫 번째 값)를 기준으로 탐색합니다. 하지만 binary_search()는 기본적으로 요소 전체를 비교하기 때문에, first 값만으로 비교하려면 사용자 정의 비교 함수(함수 객체)를 직접 작성해야 합니다.

알고리즘

시작
    keycompare 구조체를 선언한다.
        함수 operator()(const pair& v, const int& k)
        → bool 반환
            status = v.first < k
            status 반환
        함수 operator()(const int& k, const pair& v)
        → bool 반환
            status = k < v.first
            status 반환
    벡터 v를 선언한다.
    정수형 key-value 쌍을 v에 저장한다.
    push_back() 함수를 호출하여 v 벡터에 값을 삽입한다.
    sort() 함수를 호출하여 v 벡터의 모든 요소를 정렬한다.
    "정렬된 벡터"를 출력한다.
    "KEY"와 "VALUE"를 출력한다.
    for (pair& n : v)
        n의 first 값과 second 값을 출력한다.
    만약 binary_search(v.begin(), v.end(), 50, keycompare())의 결과가 참이면
        "50 exists in vector"를 출력한다.
    아니면
        "50 does not exist"를 출력한다.
    만약 binary_search(v.begin(), v.end(), 7, keycompare())의 결과가 참이면
        "7 exists in vector"를 출력한다.
    아니면
        "7 does not exist"를 출력한다.
종료

예제 코드

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

// first 값을 기준으로 pair와 int를 비교하는 함수 객체
struct keycompare {
    // (pair, int) 순서 비교
    bool operator()(const pair<int, int>& v, const int& k) {
        return (v.first < k);
    }
    // (int, pair) 순서 비교
    bool operator()(const int& k, const pair<int, int>& v) {
        return (k < v.first);
    }
};

int main() {
    vector<pair<int, int>> v;
    v.push_back(make_pair(7, 26));
    v.push_back(make_pair(6, 76));
    v.push_back(make_pair(4, 16));
    v.push_back(make_pair(5, 36));

    // first 값을 기준으로 벡터 정렬
    sort(v.begin(), v.end());

    cout << "Sorted vector" << endl;
    cout << "KEY" << '\t' << "VALUE" << endl;
    for (pair& n : v)
        cout << n.first << '\t' << n.second << endl;

    // 50 검색
    if (binary_search(v.begin(), v.end(), 50, keycompare()))
        cout << "50 exists in vector";
    else
        cout << "50 does not exist";
    cout << endl;

    // 7 검색
    if (binary_search(v.begin(), v.end(), 7, keycompare()))
        cout << "7 exists in vector";
    else
        cout << "7 does not exist";

    return 0;
}

실행 결과

Sorted vector
KEY     VALUE
4       16
5       36
6       76
7       26
50 does not exist
7 exists in vector

코드 설명

1. keycompare 구조체

keycompare는 operator()를 두 가지 방식으로 오버로드한 함수 객체입니다. 하나는 (pair, int) 순서의 비교를, 다른 하나는 (int, pair) 순서의 비교를 담당합니다.

binary_search() 내부에서는 "찾으려는 값 < 범위의 요소"와 "범위의 요소 < 찾으려는 값" 두 방향의 비교가 모두 수행됩니다. 따라서 두 오버로드가 반드시 함께 정의되어야 컴파일 오류 없이 동작합니다.

2. 정렬과 탐색

sort()는 pair의 first 값을 우선 기준으로 오름차순 정렬합니다. 정렬이 완료된 후 binary_search()에 keycompare()를 전달하면 first 값만을 기준으로 탐색이 진행됩니다.

3. 실행 결과 분석

벡터에는 4, 5, 6, 7이라는 키가 저장되어 있으므로, 50은 존재하지 않아("does not exist") 거짓이 출력되고, 7은 존재하므로("exists") 참이 출력됩니다.

💡 이진 탐색의 시간 복잡도는 O(log n)으로 매우 효율적이지만, 반드시 데이터가 사전에 정렬되어 있어야 올바른 결과를 보장합니다.