찾으려는 key 값보다 같거나 큰 숫자가 몇 번째에서 처음 등장하는지 찾기

<lower_bound 함수>

• 이진 탐색으로 원소를 탐색한다.
• 사용 조건: 탐색을 진행할 배열 혹은 벡터는 오름차순으로 정렬된 상태여야 한다. 
• 찾으려는 key값보다 같거나 큰 숫자가 몇 번째에서 처음 등장하는 찾기 위해 사용
• algorithm 헤더파일에 있다.
• 반환형은 iterator이므로 몇 번째 인덱스인지 알고 싶다면 첫번째 주소를 가리키는 배열의 이름을 빼줘야 한다.

int arr[6] ={1,2,3,4,5,6};
std::lower_bound(arr,arr+6,6) - arr; // 5반환

 

std::vector<int> arr={1,2,3,4,5,6,};
std::lower_bound(arr.begin(),arr.end(),6)-arr.begin(); //5반환

<upper_bound 함수>

• 찾으려는 key값을 초과하는 숫자가 몇 번째에서 처음 등장하는지 찾기 위해 사용
• 오름차순으로 정렬된 상태여야함.

<활용하기>

std::vector <int> arr={1,3,5,5,7,8};
std::upper_bound(arr.begin(),arr.end(),7)-std::lower_bound(arr.begin(),arr.end(),3);
/*3이상 7이하의 숫자가 몇개있는지 알고 싶을 때 사용
6-2=4반환 */

•  O(logN)으로 탐색 가능