이진 탐색(Binary Search)은 정렬된 배열 안에서 목표 값(target value)의 위치를 찾아내는 검색 알고리즘입니다. 정렬된 배열의 중간 원소와 찾고자 하는 값을 비교한 뒤, 탐색 범위를 절반씩 좁혀 나가는 방식으로 동작하며 시간 복잡도는 O(log n)으로 매우 효율적입니다.
C++ STL은 <algorithm> 헤더를 통해 이진 탐색과 관련된 대표적인 함수들을 제공합니다. 이 글에서는 C++ STL에서 사용할 수 있는 다양한 이진 탐색 함수들의 개념과 사용법을 예제 코드와 함께 자세히 살펴보겠습니다.
알고리즘
먼저 정수 값을 담은 vector를 초기화한 뒤, 아래의 STL 함수들을 활용해 탐색을 수행하고 결과를 출력합니다.
binary_search(start_pointer, end_pointer, value)
지정한 범위 내에 value가 존재하면 true, 존재하지 않으면 false를 반환합니다.
lower_bound(start_pointer, end_pointer, value)
- 컨테이너에 value가 1개만 있는 경우 → 해당 값의 위치를 가리키는 반복자(iterator) 반환
- value가 여러 개 있는 경우 → 첫 번째로 나타나는 위치 반환
- value가 존재하지 않는 경우 → value보다 큰 첫 번째 숫자의 위치 반환
upper_bound(start_pointer, end_pointer, value)
- 컨테이너에 value가 1개만 있는 경우 → value보다 큰 다음 값의 위치 반환
- value가 여러 개 있는 경우 → 마지막 value 바로 다음 위치 반환
- value가 존재하지 않는 경우 → value보다 큰 첫 번째 숫자의 위치 반환
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main() {
// 정렬된 정수 벡터 초기화
vector<int> a = {6,7,10,14,16,20};
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
cout << "The position of 7 using lower_bound ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
cout << "The position of 7 using upper_bound ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
}
실행 결과
50 does not exist
7 exists in the vector
The position of 7 using lower_bound 1
The position of 7 using upper_bound 2
결과 분석
벡터 {6, 7, 10, 14, 16, 20}에는 50이 존재하지 않으므로 binary_search는 false를 반환하고, 7은 존재하므로 true를 반환합니다. 또한 lower_bound는 7이 처음 나타나는 위치인 인덱스 1을, upper_bound는 7 바로 다음 위치인 인덱스 2를 반환합니다. 두 함수 모두 반복자를 반환하기 때문에 begin()을 빼주면 인덱스를 구할 수 있습니다.