[이분탐색] java lower bound, upper bound

매번 lower bound, upper bound 생각하는게 헷갈려 정리해본다.

상황

다음과 같이 내림차순이 아닌(오름차순이거나 같은) 배열이 있다고 가정해보자.

[1,2,2,2,2,3,4,5,6,7,8]

이때 2 값을 갖는 가장 작은 인덱스와 가장 큰 인덱스를 어떻게 구할것인가?

여기서 lower bound, upper bound 개념이 나온다.

• lower bound : key 값 이상인 값들중 가장 작은 인덱스
• upper bound : key 값 초과인 값들중 가장 작은 인덱스

// [1,2,2,2,2,3,4,5,6,7,8]
// lower bound
System.out.println(lowerBound(2)); // 1
System.out.println(lowerBound(1.5)); // 1
System.out.println(lowerBound(0)); // 0
System.out.println(lowerBound(8)); // 10

// [1,2,2,2,2,3,4,5,6,7,8]
// upper bound
System.out.println(upperBound(2)); // 5
System.out.println(upperBound(1.5)); // 1
System.out.println(upperBound(0)); // 0
System.out.println(upperBound(8)); // 11

이분 탐색

이분 탐색(binary search)를 적절하게 이용하면 찾을 수 있을거같다.

기본 적인 이분 탐색 알고리즘은 다음과 같다.

int binarySearch(int s,int e,int[] array,int key) {
    while(s<=e) {
        int mid=(s+e)/2;
        int midValue=array[mid];

        // midValue 가 key 와 같으면 mid 를 리턴한다.
        if(midValue==key) return mid;
        // midValue 가 key 보다 크면 왼쪽에서 찾는다.
        else if(midValue>key) e=mid-1;
        // midValue 가 key 보다 작으면 오른쪽에서 찾는다.
        else s=mid+1;
    }
    // 찾지 못했으면 -1 을 리턴한다.
    return -1;
}

구현 방법은 s,e를 설정해두고 중간값(midValue)을 구해 key 와 비교한다.
midValue 가 key 보다 크면 왼쪽에서 찾고 작으면 오른쪽에서 찾는다.

예를 들어 다음 배열에서 값 7 인덱스를 찾는다고 하면

[5,6,7,8,9,10,11,12]

1) s=0, e=7, mid=3, midValue=8, key=7
key(7) < midValue(8) 이므로 왼쪽에서 찾는다.

[5,6,7,8]

2) s=0, e=3, mid=1, midValue=6, key=7
key(7) > midValue(6) 이므로 오른쪽에서 찾는다.

[7,8]

3) s=2, e=3, mid=2, midValue=7, key=7
key(7) == midValue(7) 이므로 mid(2)를 리턴한다.

[7]

이제 이분 탐색을 활용해 lower bound 와 upper bound 를 구해보자.

lower bound

lower bound : key 값 이상인 값들중 가장 작은 인덱스

lower bound 의 예제 값들은 다음과 같았다.

// [1,2,2,2,2,3,4,5,6,7,8]
// lower bound
System.out.println(lowerBound(2)); // 1
System.out.println(lowerBound(1.5)); // 1
System.out.println(lowerBound(0)); // 0
System.out.println(lowerBound(8)); // 10

예제를 보면 중앙값이 key 보다 같거나 크면 왼쪽에서 찾아야한다.

다만 같은 경우에도 왼쪽에서 찾으므로 경계값(mid)도 e에 포함시킨다.

구현하면 다음과 같다.

int lowerBound(int s,int e,int[] array,int key) {
    while(s<e) {
        int mid=(s+e)/2;
        int midValue=array[mid];

        // midValue 가 key 보다 같거나 크면 왼쪽에서 찾는다.
        if(midValue>=key) e=mid;
        // midValue 가 key 보다 작으면 오른쪽에서 찾는다.
        else s=mid+1;
    }
    // s==e 이므로 s 나 e 를 리턴해도 된다.
    return e;
}

upper bound

upper bound : key 값 초과인 값들중 가장 작은 인덱스

upper bound 의 예제 값들은 다음과 같았다.

// [1,2,2,2,2,3,4,5,6,7,8]
// upper bound
System.out.println(upperBound(2)); // 5
System.out.println(upperBound(1.5)); // 1
System.out.println(upperBound(0)); // 0
System.out.println(upperBound(8)); // 11

lower bound 와 비슷하지만 key 값이 최대갑보다 크다면 list 밖의 인덱스가 리턴된다.

이번에는 중앙값이 key 보다 작거나 같으면 오른쪽에서 찾아야한다.
다만 같은 경우 s=mid+1 로 경계값(mid)를 포함시키지 않는다.

int upperBound(int s,int e,int[] array,int key) {
    while(s<e) {
        int mid=(s+e)/2;
        int midValue=array[mid];

        // midValue 가 key 보다 작으면 오른쪽에서 찾는다.
        if(midValue<=key) s=mid+1;
        // midValue 가 key 보다 크면 왼쪽에서 찾는다.
        else e=mid;
    }
    // s==e 이므로 s 나 e 를 리턴해도 된다.
    return e;
}