티스토리 뷰
이분탐색 상한선, 하한선을 구할 때
while 종료조건과 lo/hi를 갱신하는 경우 mid인지, mid + 1인지, mid - 1인지.. 너무 헷갈려서 따로 정리해보려한다.
이분탐색을 수행하기 위해서는 배열이 오름차순 정렬되어야 한다.
- 일반적인 이분탐색 (key가 존재하는 위치 반환)
static int binarySearch(int[] arr, int key) {
int lo = 0;
int hi = arr.length - 1;
while(lo <= hi) { // lo가 hi보다 커지면 종료
int mid = (lo + hi) / 2;
if(arr[mid] > key)
hi = mid - 1;
else if(arr[mid] < key)
lo = mid + 1;
else
return mid;
}
return -1; // key 값이 존재하지 않는 경우
}
- 하한선 (key와 같거나 초과하는 값이 처음으로 나타나는 위치 반환)
배열에 key가 존재한다면 key가 처음으로 나타나는 위치를 반환하며,
key가 존재하지 않는다면 key보다 큰 값이 처음으로 나타나는 위치를 반환한다.
key가 존재하지 않고 key보다 큰 값도 존재하지 않는다면, 배열의 길이를 반환해야 하므로
hi의 초기값을 arr.length - 1이 아닌 arr.length로 설정한다.
만약 배열이 2 3 4 4 6 6 6 10 일 때 6의 하한선은 4이다.
즉, key 값이 여러개라면 가장 왼쪽에 있는 값의 인덱스를 반환해야 하므로
mid 값이 key 값과 같은 경우 hi를 왼쪽으로 이동시킨다.
반환해야 할 값은 hi가 아니라 lo이므로, lo를 갱신할 경우 mid + 1를 해준다.
static int lowerBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
while(lo < hi) {
int mid = (lo + hi) / 2;
if(arr[mid] >= key)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
- 상한선 (key를 초과하는 값이 처음으로 나타나는 위치 반환)
key보다 큰 값이 존재하지 않는다면, 배열의 길이를 반환해야 하므로
hi의 초기값을 arr.length - 1이 아닌 arr.length로 설정한다.
만약 배열이 2 3 4 4 6 6 6 10 일 때 6의 상한선은 7이다.
즉, key 값이 여러개라면 가장 오른쪽에 있는 값의 인덱스를 반환해야 하므로
mid 값이 key 값과 같은 경우 lo를 오른쪽으로 이동시킨다.
반환해야 할 값은 hi가 아니라 lo이므로, lo를 갱신할 경우 mid + 1를 해준다.
static int upperBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
while(lo < hi) {
int mid = (lo + hi) / 2;
if(arr[mid] <= key)
lo = mid + 1;
else
hi = mid;
}
return lo;
}