[Algorithm/Java] Lower bound, Upper bound

배열이나 리스트에서 이분탐색을 이용해 특정 값을 찾을 때, 중복된 값을 포함하고 있을 수 있다. 그 중복값을 전부 찾거나 또는 그 중복값들을 활용해서 문제를 해결 하기 위해 upper_bound나 lower_bound를 사용한다. 

Upper bound와 Lower bound 모두 이진탐색을 활용한 알고리즘이기 때문에 이진탐색에 대해 알고 있어야 한다. 

---

 

Lower bound

lower_bound는 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 반환한다. [left, right) 의 범위내에서, 특정 find값 보다 크거나 같은 첫번째 원소의 인덱스를 반환한다. 만약 그런 원소가 없다면 right 인덱스를 반환한다. 

 

이 때 원소를 담고 있는 리스트는 모두 정렬된 상태여야 한다. 각각의 요소들 중 element < find를 만족하는 요소들은 모두 find 의 앞쪽에 있어야 한다. 그렇기 때문에 코드에서도 if(arr[mid] < find) 일 경우 left= mid+1로 변환하여 탐색 범위의 앞쪽으로 보냈다.  

private static int lowerBound(int[] arr, int find){
     int left=0;
     int right=arr.length; 
     
     while(left < right) {
         int mid= (left+right)/2; 
         
         if(arr[mid] < find) left=mid+1; 
         else right = mid; 
     }
     return right;
}

 

 

Upper bound

lower_bound는 찾고자 하는 값 이상이 처음으로 나타나는 위치인 반면에, upper_bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치를 반환한다. [left, right)의 범위 내에서, 특정 find 값 보다 큰 첫번째 원소의 인덱스를 반환한다. 

 

마찬가지로 리스트는 모두 정렬되어 있어야 하고, 각각의 요소 중 element <= find 인 값들은 그렇지 않은 값들보다 앞쪽에 있어야 한다. lower_bound 와 비교해보았을 때 등호가 포함되었는데 그 이유는 upper_bound는 find 보다 큰 값을 찾아야 하기 때문이다. (lower_bound는 이상값) 

private static int upperBound(int[] arr, int find) {
     int left=0;
     int right=arr.length; 
     
     while(left<right){
         int mid=(left+right)/2; 
         
         if(arr[mid] <= find) left=mid+1; 
         else right=mid; 
     }
     return right;
}