이분탐색 문제를 풀다보면, 만족하는 특정 값만 있는 문제 뿐만아니라 만족하는 값중 가장 작은것, 또는 만족하는 값의 다음 수를 찾는 문제들이 나온다.
이때 사용하는것이 바로 경계값찾기 - Upper Bound와 Lower Bound!!
Lower Bound?
Lower Bound는 하한값을 나타냄.
- 즉, 찾으려는 값 이상의 값이 처음으로 나타내는 위치
- 2를 찾는중이면, 111222333 이부분!
Upper Bound?
Upper Bound는 상한값을 나타냄
- 즉 찾으려는 값을 초과한 값이 처음으로 나타나는 위치
- 2를 찾는중이면, 111222333 이부분!
그렇다면 찾으려는 값이 없을때의 결과는?
5를 찾을때 1224446779가 주어진다면
Lower Bound = 1224446779 ⇒ index=6
Upper Bound = 1224446779 ⇒ index=6
따라서 위의 두가지 방식을 통해 구간의 길이를 알아 낼 수 있다. (상한-하한)
구현
이분탐색 = 중앙의 위치값을 기준으로 key값과 비교한뒤, 상한선을 내릴지 하한선을 올릴지 결정하는것.
따라서 연속된 값이 있다고 가정했을때, key값과 중앙위치의 값이 같게되었다. 이때 하한값을 찾기 위해서는 상한선을 내려야 할까 올려야할까? 당연히 하한값은 왼쪽에 있을테니 범위를 좁혀야한다. 즉, 상한선을 내려야 한다.
그럼 상한값을 찾기 위해서는? 반대로 하한선을 올린다.
이를 코드로 구현하면
//Lower bound : key값이상이 처음 나오는 인덱스 찾기
private static int lowerBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length; //-1을 하면 배열길이가 1일때 둘이 같아져버리므로 하지않음.
while(lo<hi) {
int mid = (lo+hi)/2;
if(key <= arr[mid]) hi = mid; //key이상구간을 찾는거니까 key값을 찾아도 더 앞인덱스 찾기
else lo = mid+1; //key이상구간 찾아야되는데 현재 구간이 작아서 안되니까 mid+1
}
return lo;
}
//Upper bound : key값을 초과하는 값이 처음 나오는 인덱스 찾기
private static int UpperBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length; //-1을 하면 배열길이가 1일때 둘이 같아져버리므로 하지않음.
while(lo<hi) {
int mid = (lo+hi)/2;
if(key < arr[mid]) hi = mid; //key초과구간을 찾는거니까 초과할때만 hi=mid로
else lo = mid+1; //key값을 찾으면 그를 초과하는 구간 찾아야하니까 mid+1
}
return lo;
}
위 코드를 간단히 연상해서 풀어보자면,
LowerBound는 이상값이다. 즉 현재 mid값이 target과 같거나 크면 일단 다 포함되는데, 그중에서도 가장 앞에있는 값을 찾는거니까 함부로 -1하면안된다. 즉 arr[mid] ≥ target 일때 hi = mid이고, 나머지경우엔 lo=mid+1인것이다.
UpperBound 는 초과값이다! 즉 현재 mid값이 target보다클때중 제일 앞에있는것을 찾는것이다! 따라서 arr[mid] > target이면 hi = mid인거고, 나머지경우엔 내가 찾는값이 아니니까 lo=mid+1이 된다.
관련 문제
'알고리즘' 카테고리의 다른 글
| 코딩 테스트 대비 MySQL 문법 총정리 (1) | 2024.11.24 |
|---|---|
| DP - 냅색(배낭) (5) | 2024.11.14 |