이분탐색을 활용한 Lower bound, Upper bound

이분탐색을 응용한 알고리즘이므로 이분탐색을 먼저 공부하고 오자.

 

Lower bound

찾고자 하는 값 이상이 처음 나타나는 위치이다.

Lower bound 과정

Lower bound를 찾는 과정은 아래와 같다.

1. 데이터셋의 중간 값을 가져온다.
2. 중간 값과 찾고자 하는 값을 비교한다.
    2-1. 중간 값이 찾고자 하는 값보다 작다면 left를 mid + 1로 변경한다.
    2-2. 중간 값이 찾고자 하는 값보다 크거나 같다면 right를 mid로 변경한다.
3. left < right인 경우 계속해서 반복한다.
4. 반복이 끝나면 right가 Lower bound가 된다.

 

그림을 통해 살펴보자. 아래와 같은 데이터셋이 있고, target = 13라고 가정한다. 즉, 13보다 크거나 같은 값이 처음 나타나는 위치를 찾는다.

모든 원소가 target보다 작은 경우도 존재할 수 있으므로 right를 배열의 마지막 index + 1(배열의 길이)로 설정해야 한다. 이진탐색 과정에서는 mid가 가리키는 값이 중요했지만 Lower bound에서는 right가 가리키는 값이 중요하다. 이 점을 기억하면서 진행해보자.

 

1. 현재 mid가 target보다 크므로 right를 mid로 수정한다. 이진탐색에서는 right를 mid - 1로 수정하였지만, Lower bound에서는 right를 mid로 수정한다는 것을 유의한다.

 

2. mid가 target보다 크므로 right를 mid로 수정한다.

 

3. 여기서 주의할 점은 mid가 가리키는 값이 target이 되었다고해서 반복문을 빠져나오면 안된다는 것이다. 그림에서도 알 수 있듯이 우리는 target보다 크거나 같은 값을 찾는 것이므로 과정을 한 번 더 진행해준다.

 

4. 여기서 mid가 가리기는 값이 target보다 작으므로 left = mid + 1 = 1이 될 것이고, left와 right의 값이 같아진다. 이때 반복을 종료하면 되고, right가 가리키는 값이 Lower bound이다.

---

Upper bound

찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치이다.

Upper bound 과정

Upper bound를 찾는 과정은 다음과 같다.

1. 데이터셋의 중간 값을 가져온다.
2. 중간 값과 찾고자 하는 값을 비교한다.
    2-1. 중간 값이 찾고자 하는 값보다 작거나 같다면 left를 mid + 1로 변경한다.
    2-2. 중간 값이 찾고자 하는 값보다 크다면 right를 mid로 변경한다.
3. left < right인 경우 계속해서 반복한다.
4. 반복이 끝나면 right가 Lower bound가 된다.

 

그림을 통해 살펴보자. 아래와 같은 데이터셋이 있고, target = 13라고 가정한다. 즉, 13보다 큰 값이 처음 나타나는 위치를 찾는다.

 

1. mid가 target보다 크므로 right를 mid로 수정한다.

 

2. mid가 target과 같으므로 반복문을 빠져나온다. 이때 right 값이 Upper bound가 된다.

---

응용

위와 같은 데이터 셋이 있을 때 30의 Lower bound는 arr[4] = 30이고 Upper bound는 arr[6]이 = 79다. 만약 30 이상의 값이 나타나는 첫번째 인덱스가 아닌 마지막 인덱스를 찾고 싶으면 Upper bound - 1을 해주면 된다.

 

문제에 중복 값 처리, 조건 등에 따라 여러가지를 사용할 수 있으니 관련 문제를 많이 풀어봐야겠다.