lower_bound, upper_bound, 이진탐색

lower_bound, upper_bound

• 이진 탐색으로 원소를 탐색하는 함수 제공.
• 찾으려는 key값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장 하는지 찾기위한 함
• 오름차순 정렬되어 있어야 한다.

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

int main() {

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

    // 결과 -> lower_bound(6) : 5

	return 0;
}

• lower_bound의 반환형은 iterator이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다.
• 벡터의 경우 arr.begin()을 빼면 된다.