[Algorithm] Lower Bound & Upper Bound

이진탐색을 이용해 주어진 target 값을 찾을 때, 만약 target이 배열에 여러 개 있다면, 어떤 위치가 나올지 모르게 됩니다. 이때, Lower Bound를 사용할 수 있습니다.

Lower Bound

Lower Bound는

원하는 값 target 이상의 값이 최초로 나오는 위치를 의미합니다.

즉, target보다 같거나 큰 원소의 위치들 중 가장 작은 값을 출력해야 한다는 것을 말합니다.

코드로 나타내면 다음과 같습니다.

int lowerBound(int target) {
    int left = 0;                          // 첫 번째 원소의 위치로 설정합니다.
    int right = n - 1;                     // 마지막 원소의 위치로 설정합니다.
    int minIdx = n;                        // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
    while (left <= right) {                // [left, right]가 유효한 구간이면 계속 수행합니다.
        int mid = (left + right) / 2;      // 가운데 위치를 선택합니다.
        if(arr[mid] >= target) {           // 만약에 선택한 원소가 target보다 같거나 크다면 
            right = mid - 1;               // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 right를 바꿔줍니다.
            minIdx = Math.min(minIdx, mid);// 같거나 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
        }
        else                               
            left = mid + 1;                // 작은 경우라면 left를 바꿔줍니다.
    }

    return minIdx;                         // 조건을 만족하는 최소 index 값을 반환합니다.
}

Upper Bound

Upper Bound는

원하는 값 target을 초과하는 값이 최초로 나오는 위치를 의미합니다.

코드로 나타내면 다음과 같습니다.

int upperBound(int target) {
    int left = 0;                          // 첫 번째 원소의 위치로 설정합니다.
    int right = n - 1;                     // 마지막 원소의 위치로 설정합니다.
    int minIdx = n;                        // 최소이므로, 답이 될 수 있는 값보다 더 큰 값으로 설정합니다.
    while (left <= right) {                // [left, right]가 유효한 구간이면 계속 수행합니다.
        int mid = (left + right) / 2;      // 가운데 위치를 선택합니다.
        if(arr[mid] > target) {            // 만약에 선택한 원소가 target보다 크다면 
            right = mid - 1;               // 왼쪽에 조건을 만족하는 숫자가 더 있을 가능성 때문에 right를 바꿔줍니다.
            minIdx = Math.min(minIdx, mid);// 큰 값들의 위치 중 최솟값을 계속 갱신해줍니다.
        }
        else                               
            left = mid + 1;                // 같거나 작은 경우라면 left를 바꿔줍니다.
    }

    return minIdx;                         // 조건을 만족하는 최소 index 값을 반환합니다.
}

 

Lower Bound 코드에서 등호만 제외하면, Upper Bound가 구해지는 코드가 됩니다.