[C++] lower_bound, upper_bound (이진탐색)/ 예제

 

헤더파일

#include <algorithm>

 

lower_bound

• 찾으려는  value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴
• 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함
• 사용법

lower_bound(arr, arr+n, value); // 배열
lower_bound(v.begin(), v.end(), value); // 벡터

lower_bound 의 반환형은 iterator이기 때문에 인덱스를 알고싶은 경우

lower_bound(arr, arr+n, value) - arr; // 배열
lower_bound(v.begin(), v.end(), value) - v.begin(); // 벡터

이렇게 사용하면 된다

 

upper_bound

• 찾으려는 value 값을 초과하는 숫자가 배열에서 처음으로 등장하는 위치 리턴
• 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함
• 사용법

upper_bound(arr, arr+n, value); // 배열
upper_bound(v.begin(), v.end(), value); // 벡터

upper_bound 의 반환형은 iterator이기 때문에 인덱스를 알고싶은 경우

upper_bound(arr, arr+n, value) - arr; // 배열
upper_bound(v.begin(), v.end(), value) - v.begin(); // 벡터

이렇게 사용하면 된다

 

예제

https://develop-me-z.tistory.com/115

[이코테/C++] 정렬된 배열에서 특정 수의 개수 구하기(lower_bound, upper_bound 사용)