[알고리즘] lower_bound, upper_bound : C++

 

⭐ 조건 : 탐색을 진행할 array, vector는 오름차순으로 정렬되어 있어야 한다.

lower_bound

lower_bound(3)을 진행하고 싶다.

배열 arr의 첫 시작지점 부터 탐색하면서 처음으로 3이 나오는 배열의 위치(Iterator)를 반환한다.

즉, 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 용도이다.

 

위치를 반환한다고 한 이유는 lower_bound의 반환형은 Iterator 이기 때문이다.

실제로 몇 번째 인덱스인지 알고 싶다면, 아래 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다.

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

int main() {
	int arr[6] = { 1,2,3,3,4,5,6,6,7,7 }; // 총 10개
	cout << "lower_bound(3) : " << lower_bound(arr, arr + 10, 3) - arr;

    // 결과 -> lower_bound(3) : 2
    
	return 0;
}

 

 

upper_bound

upper_bound도 lower_bound와 똑같다.

다만 처음으로 숫자가 발견되는 곳의 iterator가 아닌, 마지막으로 발견되는 곳 다음칸의 iterator가 반환된다.

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

int main() {
	int arr[6] = { 1,2,3,3,4,5,6,6,7,7 }; // 총 10개
	cout << "upper_bound(6) : " << upper_bound(arr, arr + 10, 6) - arr;

    // 결과 -> lower_bound(6) : 8
    
	return 0;
}

 

6이 마지막으로 나오는 index는 7이다. 따라서 upper_bound는 그다음칸인 8번째 칸의 iterator를 반환해 준다.

 

사용되는 상황

오름차순 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색하고자 할 때 이진 탐색 기반의 lower, upper_bound를 사용하여 O(logN)으로 탐색 가능합니다. O(N)이 불가능 할 때 유용하게 사용할 수 있습니다.

int main() {

	vector<int> arr = { 1,3,5,5,8,10,10,11,13 };
	cout << "10의 갯수 : " << upper_bound(arr.begin(), arr.end(), 10) - lower_bound(arr.begin(), arr.end(), 10);
    // 결과 2개
	return 0;
}

 

10이 마지막으로 발견된곳 다음칸의 iterator - 10이 마지막으로 발견되는 곳의 iterator 가 되어 차이인 2를 반환한다.