이분 탐색을 이용하여 어떤 리스트(배열)에서 특정 값을 찾을 때, 중복되는 값을 가지고 있을 수 있다. 그 중복값이 몇 개가 있는지 찾는 문제를 해결하기 위해 upper_bound 와 lower_bound가 존재한다.
lower_bound
: 범위(start, end) 안의 원소들 중, 특정 target 보다 크거나 같은 첫번째 원소의 인덱스를 리턴한다. 만약 그런 원소가 없다면 end 인덱스를 리턴한다.
private static int lowerBound(int[] arr, int target) {
int start = 0;
int end = arr.length;
while(start < end) {
int mid = (start + end) / 2;
if(arr[mid] >= target) {
end = mid;
}
else {
start = mid + 1;
}
}
return end;
}upper_bound
범위 (start, end) 안의 원소들 중, 특정 target보다 큰 첫번째 원소의 인덱스를 리턴한다. 만약 그런 원소가 없다면 end 인덱스를 리턴한다.
private static int upperBound(int[] arr, int target) {
int start = 0;
int end = arr.length;
while(start < end) {
int mid = (start + end) / 2;
if(arr[mid] <= target) {
start = mid + 1;
}
else {
end = mid;
}
}
return end;
}정리
이분탐색을 하기 위해서는 배열이 정렬된 상태여야 if문 조건에 만족할 수 있다. upperbound에서 target 보다 큰 인덱스 값을 설정하는 이유는 upperBound() - lowerBound()를 활용해 중복값의 개수를 찾기 때문이다.
