[알고리즘] 이분탐색 : Upper/Lower Bound(feat. Java)

Upper/Lower Bound란

Lower/Upper Bound는 이분 탐색에서 나온 개념으로 이분 탐색은 분할 정복을 이용하여 원하는 값을 적은 시간복잡도로 구할 수 있는 유용한 알고리즘이다.(분할정복 모르시는 분은 아래 링크 참고!!)

 

https://codingralro.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-feat-Java

[알고리즘] 분할정복 (feat. Java)

 

Upper/Lower Bound란,  중복을 허용하는 값들의 리스트(정렬된)에서 원하는 값 중 제일 첫번째 나오는 위치를 찾는 것은 Lower Bound, 원하는 값을 처음으로 초과하는 위치를 찾는 것을 Upper Bound라고 한다.

 

 

 

Lower Bound 예제 및 간략 코드

정렬된 배열 { 2, 2, 3, 4, 4, 6, 7 } 이 있고 값 3을 찾는다고 하자. 이 때에 값 2이 중복될 경우, 제일 처음 오는 값의 위치를 찾아야 한다면, 아래와 같은 과정을 거친다.

 

• start = 1, end = 7 ( 배열의 첫번째 인덱스를 편의상 1이라고 지정, 실제론 0부터 시작)
• mid = (1 + 7) / 2 = 4 번째 값을 2와 비교
• 4번째 값이 4는 2보다 큼
• 일반적인 이분탐색에서는 mid값이 원하는 값보다 큰 경우를 다루지만, lower bound에서는 크거나 같은 경우를 다룬다. 이 때에 크거나 같은 경우 end = mid - 1이 아닌 end = mid로 지정해줌
• start = 1, end = 4
• mid = (1 + 4 ) / 2 = 2 번째 값을 2와 비교
• mid의 값이 2가 2보다 같거나 크므로 end = mid로 지정
• start = 1, end = 2
• mid = (1 + 2) / 2 = 1 번째 값을 2와 비교
• mid의 값이 2가 2보다 같거나 크므로 end = mid로 지정
• start = 1, end = 1로 같아지므로 while문 종료
• 위지는 즉, start or end이다. 

 

일반적인 이분탐색과의 차이점은 코드를 통해 자세히 알아보겠다.

int[] arr = {2, 2, 3, 4, 4, 6, 7};
int key = 2;

public int lowerBound(int[] arr, int key){
    int start = 0;
    int end = arr.length - 1;
    
    //end == start면 그 값이 lower bound이므로 종료
    while(start < end ) { //일반탐색 : start <= end
        int mid = (start + end) / 2;
    
        //일반적인 이분탐색의 경우 mid의 값이 찾는 값이면 mid를 리턴
        /*
        if(arr[mid] == key) {
            return mid;
        }
        */
    
        if(arr[mid] >= key)
            end = mid;
        else
            start = mid + 1;
    }
    return start;
}

 

 

 

Upper Bound

Upper Bound는 lower bound의 코드를 살짝만 수정하여 주면 된다. 초과하는 첫번째 값을 찾아주는 것이기 때문에 mid값이 원하는 값보다 작거나 같을 경우, start를 mid + 1로 초기화하는 것이다. (해당 값을 초과하는 처음 값을 찾는 것이기 때문에 mid값이 같은 경우에도 mid + 1을 해줌)

 

int[] arr = {2, 2, 3, 4, 4, 6, 7};
int key = 2;

public int lowerBound(int[] arr, int key){
    int start = 0;
    int end = arr.length - 1;
    
    //end == start면 그 값이 upper bound이므로 종료
    while(start < end ) { 
        int mid = (start + end) / 2;
    
        if(arr[mid] > key)
            end = mid;
        else
            start = mid + 1;
    }
    return start;
}