lower_bound & upper_bound 함수

<algorithm> 헤더에 정의되어 있는 함수

1. lower_bound : 범위 안의 원소들 중, value보다 작지 않은(크거나 같은) 첫번째 원소의 위치를 반복자로 반환

이진탐색(binary search) 기반의 탐색법

(이진탐색 기반이므로, 범위 안의 원소들은 정렬된 상태여야 한다.)

사용법 

lower_bound(범위 시작 위치, 범위 마지막 위치, value)

2. upper_bound : 범위 안의 원소들 중, value보다 큰 첫번째 원소의 위치를 반복자로 반환

이진탐색 기반의 탐색법

사용법

upper_bound(범위 시작 위치, 범위 마지막 위치, value)

---

사용코드 예시) vector 사용 

#include <stdio.h>
#include <algorithm>    
#include <vector>
using namespace std;
int main()
{
    int arr[8] = { 0,10,20,30,10,20,40,50 };
    vector<int> vec(arr, arr + 8);
 
    //lower_bound와 upper_bound는 이분탐색 이용 -> 정렬되있어야함
    sort(vec.begin(), vec.end()); // 0 10 10 20 20 30 40 50
 
    vector<int>::iterator lower, upper;
    lower = lower_bound(vec.begin(), vec.end(), 20); // 20 이상인 수의 iterator를 찾음
    upper = upper_bound(vec.begin(), vec.end(), 20); // 20 초과인 수의 iterator를 찾음
 
    //인덱스를 출력하려면 lower_bound()-vector.begin(), upper_bound()-vector.begin()
    printf("lower_bound index : %d\n", lower - vec.begin());
    printf("upper_bound index : %d\n", upper - vec.begin());
    
    return 0;
}
 
 

출력)

인덱스	0	1	2	3	4	5	6	7
값	0	10	10	20	20	30	40	50

20 이상 값의 첫번째 인덱스 값 : 3

20 초과 값의 첫번재 인덱스 값 : 5