[이분탐색] Upper / Lower Bound

이분(이진)탐색에서 항상 헷갈리던 Upper / Lower Bound 에 대해서 복습하자.
feat. (백준 14003, 소프티어 3307의 LIS 문제를 해결하며.)

---

개요

 

이분 탐색은 정렬된 요소중 찾고 싶은 값, target(key)을 빠르게 찾는 방법이다. O(logN)

 

단순히 타겟을 찾는 것을 넘어서, 이진 탐색의 원리를 확장하여 ‘Upper Bound’와 ‘Lower Bound’ 개념을 적용함으로써, 데이터 집합 내에서 특정 값의 범위를 정확하고 빠르게 찾을 수 있어야한다.

---

개념 비교하기

 

Upper Bound는 주어진 값보다 큰 첫 번째 요소를 찾는다. 

Lower Bound는 주어진 값 이상의 첫 번째 요소를 찾는다.

 

idx	0	1	2	3	4	5	6	7	8
value	1	1	2	2	2	3	3	3	4

 

찾고 싶은 value, 즉 target = 2로 가정한다.

 

Upper Bound (target = 2)

target 초과 첫 요소 -> value = 3, idx = 5

 

Lower Bound (target = 2)

target 이상 첫 요소 -> value = 2, idx = 2

---

코드로 비교하기

 

hi = arr.length와 while (lo < hi)를 사용하는 방식은 범위 탐색, 예를 들어 upper bound 또는 lower bound를 찾는 상황에 사용

public static int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
     
        return lo;
}

 

public static int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }

        return lo;
}

 

 

여러 참고자료를 통해서 가장 깔끔하게 작성할 수 있는 자바 코드를 작성했다.

결론적으로 현재 바라보는 arr[mid]와 target 을 비교하는 조건문에서 "=" 하나가 추가됐을 뿐이다.

심오하다 심오해. 문제를 해결할 때는 분명 복잡했단말입니다.

 

이렇게 간단한줄 알았다면 이해하지않고 외웠을게 분명하다.

 

 

아래는 테스트하기 좋은 코드입니다. 출력으로 간단히 디버깅이 가능해요.

lo와 hi가 같은 값을 반환한다는 것을 알 수 있다!

그저 mid가 중요한 값이라고 생각했는데, 결과적으로 lo와 hi가 반환되게 만드는 반복문의 조건이 중요했다.

이게 헷갈림의 포인트가 아니였을까?

package test;

public class BoundExample {

    public static void main(String[] args) {
        int[] array = {1, 1, 2, 2, 2, 3, 3, 3, 4};
        int target = 2;

        int lowerBoundIndex = lowerBound(array, target);
        int upperBoundIndex = upperBound(array, target);

        System.out.println("Lower Bound of target " + target + ": index = " + lowerBoundIndex + ", value = " + array[lowerBoundIndex]);
        System.out.println("Upper Bound of target " + target + ": index = " + upperBoundIndex + ", value = " + array[upperBoundIndex]);
    }

    public static int lowerBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            System.out.printf("Lower Bound - lo: %d, hi: %d, mid: %d, arr[mid]: %d\n", lo, hi, mid, arr[mid]);
            if (arr[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        System.out.printf("Lower Bound result - lo: %d, hi: %d\n", lo, hi);
        return lo;
    }

    public static int upperBound(int[] arr, int target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            System.out.printf("Upper Bound - lo: %d, hi: %d, mid: %d, arr[mid]: %d\n", lo, hi, mid, arr[mid]);
            if (arr[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        System.out.printf("Upper Bound result - lo: %d, hi: %d\n", lo, hi);
        return lo;
    }
}

 

 

 

추가 (배열에서 정확한 값을 찾는 경우)

정확한 값을 찾기 위해서는 hi를 arr.length - 1로 설정하고, while (lo <= hi)를 사용!
이렇게 하면 배열의 모든 요소가 제대로 탐색되며, 필요한 값을 정확히 찾을 수 있습니다.

public static int findExact(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;  // 배열의 마지막 인덱스를 hi로 설정

    while (lo <= hi) {  // lo와 hi가 같아질 때까지 반복
        int mid = (lo + hi) / 2;

        if (arr[mid] == target) {
            return mid;  // 정확한 값을 찾았을 때, 해당 인덱스를 반환
        } else if (arr[mid] < target) {
            lo = mid + 1;  // target이 더 크면 lo를 증가시켜 검색 범위를 오른쪽으로 좁힘
        } else {
            hi = mid - 1;  // target이 더 작으면 hi를 감소시켜 검색 범위를 왼쪽으로 좁힘
        }
    }

    return -1;  // 값을 찾지 못한 경우 -1 반환
}

 

추가 (특정 조건을 만족하는 최대값을 찾는 경우)

end는 존재하는 값으로 설정해야 한다.
범위 탐색(lower, upper bound)처럼 arr.length를 사용하는 것이 아니라
정확한 값을 탐색할 때의 arr.length-1을 사용하는 것과 같은 의미다.

while (start <= end) {
    int mid = (start + end) / 2;

    if (dijkstra(mid)) {
        start = mid + 1;  // mid가 조건을 만족하므로, 더 큰 값을 탐색
    } else {
        end = mid - 1;  // mid가 조건을 만족하지 않으므로, 더 작은 값을 탐색
    }
}

System.out.println(end);  // 최종적으로 end에는 조건을 만족하는 최대값이 저장됨
System.out.println(start);  // 최종적으로 start에는 조건을 만족하는 최소값이 저장됨

---

후기

 

원래 복잡할 것이라고 생각했던 알고리즘이 의외로 간단하게 해결되어서 적당히 이해하고 외우려고 한다.

 

중요한건 upper, lower bound를 구분할 수 있는 분석 능력이라고 생각한다.

 

또, upper, lower bound를 구분할 필요가 없는 이분 탐색 문제라고 해도, PS할 때 되게 자주나오는 것 같다. 특히 히든(엣지)케이스를 해결하기 위해서는 입력 값의 범위를 보고 탐색 시간을 줄여야함을 인지하는게 중요하다고 생각한다.

선형 탐색 O(N) -> 이분 탐색 O(logN)