C++ STL 이진 탐색(Binary Search)이란?
이진 탐색은 배열의 중간값과 찾고자 하는 요소를 비교하고, 비교 결과에 따라 탐색 범위를 절반씩 나누어가며 검색을 수행하는 알고리즘입니다. 원하는 요소를 찾을 때까지 이 과정을 반복합니다.
이진 탐색을 적용하려면 배열이 반드시 정렬되어 있어야 한다는 점을 기억해야 합니다.
이진 탐색의 시간 복잡도는 로그(logarithmic) 순서로 매우 효율적입니다. 그렇기 때문에 프로그래머라면 알고리즘을 직접 구현하는 것뿐만 아니라, 코딩 시간을 크게 단축할 수 있는 관련 단축 함수들도 함께 익혀두는 것이 중요합니다. C++ 표준 템플릿 라이브러리(STL)에는 이진 탐색과 관련된 유용한 함수들이 포함되어 있으며, 이번 글에서는 대표적인 세 가지 함수를 자세히 살펴보겠습니다.
1. lower_bound — 하한 탐색
lower_bound는 지정한 요소가 처음 등장하는 위치를 반환하는 함수입니다.
문법
lower_bound(start_pointer, end_pointer, element)
각 매개변수의 의미는 다음과 같습니다.
start_pointer : 탐색 구조의 시작 지점 메모리 위치를 담고 있는 포인터(반복자)입니다.
end_pointer : 탐색 구조의 끝 지점 메모리 위치를 담고 있는 포인터입니다.
element : 함수를 통해 찾고자 하는 요소입니다.
함수는 찾으려는 요소의 인덱스에 해당하는 값을 반환하며, 상황에 따라 반환 값이 달라집니다.
- 요소가 구조 안에서 한 번만 등장하는 경우 → 해당 요소의 위치를 반환합니다.
- 요소가 구조 안에서 여러 번 등장하는 경우 → 첫 번째 요소의 위치를 반환합니다.
- 요소가 구조 안에 존재하지 않는 경우 → 해당 요소보다 큰 값 중 가장 작은 값의 위치를 반환합니다.
특정 요소의 실제 인덱스를 얻으려면 반환 값에서 구조의 시작 위치(begin())을 빼주면 됩니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"lower_bound 함수로 찾은 요소 7의 위치 :";
cout<<"\nCase 1 : 요소가 배열에 한 번만 존재할 때 ";
cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : 요소가 배열에 여러 번 존재할 때 ";
cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : 요소가 배열에 존재하지 않을 때 ";
cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}실행 결과
lower_bound 함수로 찾은 요소 7의 위치 : Case 1 : 요소가 배열에 한 번만 존재할 때 2 Case 2 : 요소가 배열에 여러 번 존재할 때 2 Case 3 : 요소가 배열에 존재하지 않을 때 4
2. upper_bound — 상한 탐색
upper_bound는 전달된 요소보다 큰 값이 처음 등장하는 위치를 반환하는 함수입니다.
문법
upper_bound(start_pointer, end_pointer, element)
매개변수의 의미는 lower_bound와 동일합니다.
start_pointer : 탐색 구조의 시작 지점 메모리 위치를 담고 있는 포인터입니다.
end_pointer : 탐색 구조의 끝 지점 메모리 위치를 담고 있는 포인터입니다.
element : 기준이 되는 요소입니다.
함수는 전달된 요소의 값보다 큰 값을 가지는 첫 번째 요소의 인덱스를 반환하며, 상황별 동작은 다음과 같습니다.
- 요소가 구조 안에서 한 번만 등장하는 경우 → 해당 요소 바로 다음(더 큰 값)의 위치를 반환합니다.
- 요소가 구조 안에서 여러 번 등장하는 경우 → 마지막으로 등장한 요소의 다음 위치를 반환합니다.
- 요소가 구조 안에 존재하지 않는 경우 → 해당 요소보다 큰 값 중 가장 작은 값의 위치를 반환합니다.
마찬가지로 실제 인덱스를 구하려면 반환 값에서 시작 위치(begin())을 빼주면 됩니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"upper_bound 함수로 찾은 요소 7의 위치 :";
cout<<"\nCase 1 : 요소가 배열에 한 번만 존재할 때 ";
cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : 요소가 배열에 여러 번 존재할 때 ";
cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : 요소가 배열에 존재하지 않을 때 ";
cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}실행 결과
upper_bound 함수로 찾은 요소 7의 위치 : Case 1 : 요소가 배열에 한 번만 존재할 때 3 Case 2 : 요소가 배열에 여러 번 존재할 때 4 Case 3 : 요소가 배열에 존재하지 않을 때 4
3. binary_search — 요소 존재 여부 확인
binary_search는 특정 요소가 구조 안에 존재하는지 여부만 확인하는 함수입니다. 위치 정보가 필요 없고 존재 여부만 판단하면 될 때 유용하게 사용됩니다.
문법
binary_search(start_pointer, end_pointer, element)
매개변수의 의미는 앞선 두 함수와 같습니다.
start_pointer : 탐색 구조의 시작 지점 메모리 위치를 담고 있는 포인터입니다.
end_pointer : 탐색 구조의 끝 지점 메모리 위치를 담고 있는 포인터입니다.
element : 존재 여부를 확인할 요소입니다.
요소가 구조 안에 존재하면 true를, 존재하지 않으면 false를 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
cout<<"배열에서 찾을 요소는 21입니다\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
cout<<"요소를 찾았습니다";
else
cout<<"요소를 찾지 못했습니다";
cout<<"\n배열에서 찾을 요소는 5입니다\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
cout<<"요소를 찾았습니다";
else
cout<<"요소를 찾지 못했습니다";
}실행 결과
배열에서 찾을 요소는 21입니다 요소를 찾았습니다 배열에서 찾을 요소는 5입니다 요소를 찾지 못했습니다
마무리 정리
STL의 세 가지 이진 탐색 함수는 각각 용도가 다릅니다. lower_bound는 요소가 처음 등장하는 위치(또는 삽입 가능한 하한 위치)를, upper_bound는 요소보다 큰 값이 처음 등장하는 위치를, binary_search는 단순히 요소의 존재 여부를 확인할 때 사용합니다. 세 함수 모두 정렬된 데이터를 전제로 동작하므로, 사용 전 반드시 컨테이너가 정렬되어 있는지 확인하는 습관을 들이면 좋습니다. 로그 시간 복잡도 덕분에 대용량 데이터에서도 빠른 성능을 보장하므로, 실전 코딩과 알고리즘 문제 해결에서 적극적으로 활용해 보시기 바랍니다.