백준 10816 lower_bound upper_bound로 풀기

목표: 백준 10816 lower_bound, upper_bound로 문제 풀기

환경: mac OS Mojave 10.14, CLion

로직

lower_bound 함수를 통해서 찾으려는 수보다 작거나 같은 수 중에서 가장 큰 값의 인덱스를 반환

upper_bound 함수를 통해서 찾으려는 수보다 큰 수 중에서 가장 작은 값의 인덱스를 반환

답 : upper_bound - lower_bound

lower_bound: 오름차순으로 정렬되어있는 배열에서 찾고자 하는 key 값보다 작거나 같은 수 중에서 가장 큰 수의 인덱스를 반환합니다. 처음 lower_bound를 통해 값을 찾고자 하는 구간을 [0, 마지막인덱스+1]로 설정합니다. 구간 내의 중간 위치를 mid라고 할때, arr[mid] >= key 이면 [left, mid] , arr[mid] < key 이면 [mid+1, right] 로 arr[mid] 값을 통해 탐색구간을 좁혀갑니다. 탐색하는 구간에는 key값과 같거나 key보다 작은 값들이 존재합니다.

처음 lower_bound 탐색하는 구간을 마지막인덱스+1로 하는 이유는 해당배열에서 가장 큰 값보다 더 큰 수를 찾을 때에는 마지막 인덱스+1로 표현을 해야되기 때문입니다.

left : 찾으려는 수보다 작은 수 right : 찾으려는 수보다 크거나 같은 수

lower_bound 과정 1 2 3 4 5 right는 항상 key값보다 크거나 같은 수로 유지됩니다.

lower_bound는 이렇게 작거나 같은 수중 가장 큰 값으로 범위를 좁혀가요.

        if( nums[mid] <= num) { <- lower_bound

        if( nums[mid] < num) { <- upper_bound 

upper_bound는

left : 찾으려는 수보다 작거나 같은 수 right : 찾으려는 수보다 큰 수

그래서 left에는 key값도 포함합니다. right값은 항상 key값보다 크고요.

lower_bound와 left, right의 변수의 의미에 차이가 있습니다.

이분탐색, lower_bound, upper_bound에서는 이렇게 left, right 변수의 의미를 명확히 두는게 중요합니다.

SourceCode