💡이분 탐색(이진 탐색/Binary Search)
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- 시작점, 끝점, 중간점을 이용하여 탐색한다.
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례한다. 즉, 시간 복잡도는 O(logN)이다.
탐색 과정
- 정렬된 배열에서 시작점, 끝점, 중간점을 설정한다.
- 중간점의 값과 찾고자 하는 값을 비교한다.
- 만약 중간점의 값이 찾고자 하는 값과 일치하면, 탐색을 종료한다.
- 중간점의 값이 찾고자 하는 값보다 작으면, 시작점을 중간점 다음 위치로 이동한다.
- 중간점의 값이 찾고자 하는 값보다 크면, 끝점을 중간점 이전 위치로 이동한다.
- 시작점과 끝점이 만나거나 교차할 때까지 위의 과정을 반복한다.
- 원하는 값을 찾거나 시작점과 끝점이 교차할 경우, 탐색을 종료한다.
코드 구현
- 재귀적 구현
int binarySearch(vector<int>& arr, int target, int start, int end) {
if (start > end)
return -1;
int mid = (start + end) / 2;
if (arr[mid] == target)
return mid;
// 찾는 수가 더 작다면, 검사 범위를 더 작게 잡아야 한다.
if (arr[mid] > target)
return binary_search(arr, target, start, mid - 1);
// 찾는 수가 더 크가면, 검사 범위를 더 크게 잡아야 한다.
else
return binary_search(arr, target, mid + 1, end);
}- 반복문 구현
int binarySearch(vector<int>& arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}- C++ STL
필요한 헤더: algorithm
1. binary_search() 함수
binary_search(ForwardIt first, ForwardIt last, const T& value)
- first: 검색을 시작할 범위의 시작 반복자(Iterator)
- last: 검색을 종료할 범위의 끝 반복자(Iterator)
- value: 찾고자 하는 값
주어진 반복자의 [시작주소, 끝주소)에서 찾고자 하는 값을 이진 탐색을 사용하여 찾아주는 함수이다. 이 함수는 정렬된 상태에서 빠르게 값을 찾을 때 사용한다. 만약 찾는 값이 존재하면 true를, 그렇지 않으면 false를 반환한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
int target = 3;
if (binary_search(vec.begin(), vec.end(), target))
cout << "Value found!";
else
cout << "Value not found.";
return 0;
}2. lower_bound() 함수
lower_bound(ForwardIt first, ForwardIt last, const T& value)
- first: 검색을 시작할 범위의 시작 반복자(Iterator)
- last: 검색을 종료할 범위의 끝 반복자(Iterator)
- value: 찾고자 하는 값
오름차순으로 정렬된 컨테이너에서 사용되며, 특정 값 이상이 처음으로 나타나는 위치를 이분 탐색 기반으로 찾아준다.
lower_bound 함수는 찾고자 하는 값 이상이 처음으로 나타나는 위치를 가리키는 반복자를 반환한다.
[동작]
주어진 범위 [first, last)에서 이진 탐색을 수행하여 찾고자 하는 값 이상이 처음으로 나타나는 위치를 찾는다.
만약 해당 값이 존재하지 않으면, 다음으로 큰 값의 위치를 반환한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1, 2, 3, 4, 4, 4, 5, 6 };
int target = 3;
if (lower_bound(vec.begin(), vec.end(), target) != vec.end()) {
cout << target << " 이상이 처음으로 나타나는 위치: "
<< lower_bound(vec.begin(), vec.end(), target) - vec.begin();
}
else {
cout << target << " 이상인 값이 발견되지 않았습니다.";
}
return 0;
}
3. upper_bound() 함수
upper_bound(ForwardIt first, ForwardIt last, const T& value)
- first: 검색을 시작할 범위의 시작 반복자(Iterator)
- last: 검색을 종료할 범위의 끝 반복자(Iterator)
- value: 찾고자 하는 값
오름차순으로 정렬된 컨테이너에서 사용되며, 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치를 이분 탐색 기반으로 찾아준다.
upper_bound 함수는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치를 가리키는 반복자를 반환한다.
[동작]
주어진 범위 [first, last)에서 이진 탐색을 수행하여 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치를 찾는다.
만약 해당 값이 존재하지 않으면, 다음으로 큰 값의 위치를 반환한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1, 2, 3, 4, 4, 4, 5, 6 };
int target = 3;
if (upper_bound(vec.begin(), vec.end(), target) != vec.end()) {
cout << target << "보다 큰 값이 처음으로 나타나는 위치: "
<< upper_bound(vec.begin(), vec.end(), target) - vec.begin();
}
else {
cout << target << "보다 큰 값이 발견되지 않았습니다.";
}
return 0;
}lower_bound()와 upper_bound() 활용 예시
- 범위 내 특정 값의 개수 세기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1, 2, 3, 4, 4, 4, 5, 6 };
int target = 4;
// lower_bound와 upper_bound를 사용하여 특정 값의 범위를 찾음
auto lower = lower_bound(vec.begin(), vec.end(), target);
auto upper = upper_bound(vec.begin(), vec.end(), target);
// 특정 값의 개수는 upper_bound - lower_bound
int count = upper - lower;
cout << target << "은 " << count << "개 있다.";
return 0;
}