[Algorithm] 상계/하계(Upper Bound/Lower Bound)

상계/하계(Upper Bound/Lower Bound)?

Lower Bound와 Upper Bound는 이진 탐색을 기반으로 하여 경곗값을 찾는 알고리즘이다.

이진 탐색을 기반으로 하기 때문에 당연히 데이터가 정렬되어 있어야 한다.

 

값을 찾을 때, 원하는 값이 없을 때 못찾았다는 신호(-1, false 등)를 반환하는 일반적인 이진 탐색과 달리 Upper Bound와 Lower Bound를 이용하면 찾고자 하는 값 또는 그 값의 초과값이 처음 나타나는 위치를 찾을 수 있다.

 

때문에 주로 특정 값을 어느 위치에 삽입해야 하는지 탐색할 때 많이 사용한다.

 

 

상계 (Upper Bound)

Upper Bound는 찾고자 하는 값(target)보다 큰 값의 처음 위치를 반환한다.

 

구현

public class UpperBound {

    public static void main(String[] args) {
        int[] array = {1, 3, 3, 3, 4, 6, 7, 7, 14, 14, 16, 20};
        int target = 7;

        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;

            if (array[mid] <= target) {
                left = mid + 1;
                continue;
            }
            right = mid;
        }

        System.out.println("right = " + right);
        System.out.println("array[right] = " + array[right]);
    }
}

구현을 살펴보면, mid값이 target값과 같아도 left값을 갱신시켜주는 것을 볼 수 있다. 이렇게 함으로써 target값과 같음에도 범위를 줄여나가며, 원래 target값보다 큰 값이 나오도록 할 수 있다.

 

또한 일반 이진 탐색과 달리, right 값을 mid - 1로 갱신시키지 않고 mid값으로 갱신시키는 것을 확인할 수 있다.

이렇게 하면 Upper Bound 값은 항상 right 값에 위치하게 된다. 때문에 마지막에 결괏값을 출력할 때도 right값을 이용하여 출력한다.

 

 

하계 (Lower Bound)

Lower Bound는 찾고자 하는 값(target)보다 크거나 같은 값의 처음 위치를 반환한다.

 

구현

public class LowerBound {

    public static void main(String[] args) {
        int[] array = {1, 3, 3, 3, 4, 6, 7, 7, 14, 14, 16, 20};
        int target = 7;

        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;

            if (array[mid] < target) {
                left = mid + 1;
                continue;
            }
            right = mid;
        }

        System.out.println("right = " + right);
        System.out.println("array[right] = " + array[right]);
    }
}

Lower Bound의 구현은 Upper Bound와 유사하다. 다른 점은 left 갱신 조건이다. target 값보다 크거나 같은 첫 위치를 찾는 것이기 때문에 Upper Bound와 달리 target보다 작을 경우에만 갱신하도록 했다.

right 값은 Upper Bound와 같이 mid로 갱신하기 때문에 결괏값이 항상 right에 위치한다.