이전에 살펴본 이진검색 알고리즘은 만약 검색하는 값과 동일한 값이 배열의 여러 element 에 존재한다면, 해당 element 들의 모든 인덱스를 찾아올 수 없다. 따라서 중복값을 찾으려면 다른 알고리즘이 필요하게 되는데
우선, 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 찾고
특정 값보다 처음으로 큰 값이나 나오는 위치를 찾는다면 중복값들의 모든 인덱스를 출력할 수 있게된다.
그렇다면 JAVA 로 특정 값보다 처음으로 큰 값이나 나오는 위치를 찾는
lowerBound 메소드를 구현해 보자
static int lowerBound(int[] arr, int value){
int l = 0;
int r = arr.length; // value 가 배열에 있는 어떠한 값보다 클 경우, 배열의 마지막 인덱스를 넘기지 않기 위함.
int mid;
while (l < r){
mid = (l + r)/2;
if(value <= arr[mid])
r = mid;
else
l = mid+1;
}
return l;
}
다음으로 JAVA 특정 값보다 처음으로 큰 값이나 나오는 위치를 찾는
upperBound 메소드를 구현해 보자
static int upperBound(int arr[], int value) {
int l = 0;
int r = arr.length;
int mid;
while (l < r) {
mid = (l + r) / 2;
if (value >= arr[mid]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}