[C++] 이분 탐색 메서드 - binary_search, lower_bound, upper_bound

이분 탐색은 정렬된 배열에서 특정 요소를 빠르게 찾는 알고리즘이다. 배열 내의 중간 요소를 선택하고 찾고자 하는 요소와 비교하여 해당 요소가 배열의 중간 요소보다 큰지 작은 지를 판단하고 탐색 범위를 절반으로 줄이는 방식이다. 

 

C++에서 이분 탐색 메서드들이 정의되어 있다.

 

1. binary_serach

• 주어진 정렬된 범위에서 특정 원소가 있는지 확인한다.
• 찾는 원소가 있으면 true, 없으면 false를 리턴한다.

std::vector<int> nums = {1, 2, 3, 4, 5, 6};
bool found = std::binary_search(nums.begin(), nums.end(), 3); // true 반환

2. lower_bound

• 주어진 정렬된 범위에서 특정 원소 이상인 첫 번째 원소의 위치를 반환한다. 찾지 못하면 arr.end()를 반환한다.

vector<int> nums = {1, 2, 2, 4, 4, 6};
auto it = lower_bound(nums.begin(), nums.end(), 3);
if (it != nums.end()) {
    std::cout << "3 이상인 첫 번째 요소는 " << *it << "입니다." << std::endl;
} else {
    std::cout << "3 이상인 요소를 찾지 못했습니다." << std::endl;
}

3. upper_bound

• 주어진 정렬된 범위에서 특정 원소보다 큰 첫 번째 원소의 위치를 반환한다. lower_bound와 다른 점은 찾는 원소 이상인 위치를 반환하는게 아니라 찾는 원소보다 큰 위치를 반환한다는 것이다. 

vector<int> nums = {1, 2, 2, 4, 4, 6};
auto it = upper_bound(nums.begin(), nums.end(), 3);
if (it != nums.end()) {
    std::cout << "3보다 큰 첫 번째 요소는 " << *it << "입니다." << std::endl;
} else {
    std::cout << "3보다 큰 요소를 찾지 못했습니다." << std::endl;
}

4. equal_bound

• 주어진 정렬된 범위에서 특정 원소의 범위를 반환한다.

vector<int> nums = {1, 2, 2, 4, 4, 6};
auto range = equal_range(nums.begin(), nums.end(), 4);
if (range.first != nums.end()) {
    std::cout << "4의 범위: [" << *range.first << ", " << *(range.second - 1) << "]" << std::endl;
} else {
    std::cout << "4를 찾지 못했습니다." << std::endl;
}

위의 메서드들은 정렬된 배열에서 사용해야한다는 주의점이 있다. 또 중복된 값을 다룰 때 사용할 수 있다.

 

1. lower_bound로 중복된 값 중 첫 번째로 등장한 요소를 선택한다.

2. upper_bound로 중복된 값 중 마지막으로 등장한 요소를 선택한다.

3. equal_bound로 중복된 값의 범위를 설정한다.