이분탐색 알고리즘(Upper Bound, Lower Bound)

오름차순으로 정렬된 배열에서 찾고자 하는 값 key가 있을 때,

Upper Bound는 key보다 큰 첫번째 위치(초과)를 반환한다.

Lower Bound는 key보다 크거나 같은 첫번째 위치(이상)블 반환한다.

 

예) 배열 {1, 3, 3, 5, 7}이 있을 때,

key = 3이면

Upper Bound = 3(인덱스), Lower Bound = 1(인덱스)가 된다.

 

key = 2이면

Upper Bound = 1(인덱스), Lower Bound = 1(인덱스)가 된다.

 

lower bound, 하한은 찾고자 하는 값 '이상'의 값이 처음으로 나타나는 위치를 의미한다.

즉, 왼쪽부터 볼 때 찾고자 하는 값이 같거나 큰 경우를 처음 만나는 위치를 의미한다.

 

 

key 값이 4일 때 처음 마주하는 키 값 이상을 갖고 있는 인덱스는 3이다.

즉, lower bound의 값은 3이 된다.

 

upper bound, 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다.

키 값이 4일 때 4를 초과한 값을 처음 만나는 위치의 인덱스는 6이다.

그래서 upper bound의 값은 6이다.

 

추가로 찾는 값이 없는 경우,

키값이 5일 때 배열에는 5가 없다.

이럴 경우, index 6이 lower bound이자 upper bound이기도 하다.

 

※ 중복 원소의 길이 = upper bound - lower bound 로 구할 수 있다.

 

이분 탐색의 원리는 중앙 위치의 값(mid)을 기준으로 key 값과 비교 한 뒤, 상한선(end)를 내릴 것인지, 하한선(start)을 올릴 것인지를 결정하는 것이다.

 

예를 들어, 중앙 위치의 값이 앞뒤로 연속된 중복값을 갖고 있다고 할 때, key값과 중앙 위치의 값이 같게 되었다. 이 때, 하한값(lower bound)을 찾기 위해서는 상한선(end)을 내려야 할까, 하한선(start)을 올려야 할까?

가장 하한값을 찾는 다는 것은 같은 값이 있는 요소들의 가장 왼쪽을 찾아야 한다는 것이다. 즉, 왼쪽으로 범위를 좁여햐 한다. 따라서 탐색구간의 상한선을 내려야 한다.

 

반대로 상한 값을 찾기 위해서는 하한과 반대로 오른쪽으로 범위를 좁혀나가야 하기 때문에 탐색 구간의 하한선을 올려야 한다.

 

 

 

 

* Upper Bound

  - key 보다 큰 첫번째 위치를 찾는 것이기 때문에 arr[mid] == key일 때도 start값을 m+1로 증가시킨다.

  - end = mid 이므로 최종 연산 후에는 언제나 결과값이 end에 위치하게 된다. 그래서 return end를 한다.

// key 보다 큰 첫번째 위치 반환
int upperBound(int start, int end, int key, int arr[]) {
    while (start < end) {
        int mid = (start+end)/2;
        // 중간 위치의 값이 키 값보다 같거나 작을 경우
        // 범위를 좁히기 위해선 하한선(start)를 올려야 한다.
        if (arr[mid] <= key) {
            start = mid + 1;
        }
        // 중간 위치의 값이 키 값보다 클 경우
        // 범위를 좁히기 위해서 상한선(end)를 내려야 한다.
        else { // key < arr[mid]
            end = mid;
        }
    }
    return end;
}

 

* Lower Bound

  - 키 값보다 arr[mid]가 작을 때만 start를 변경한다.

  - end = mid 이므로 최종 연산 후에는 언제나 결과값이 end에 위치하게 된다. 그래서 return end를 한다.

// key 보다 크거나 같은 첫번째 위치 반환
int lowerBound(int start, int end, int key, int arr[]) {
    while (start < end) {
        int mid = (start+end)/2;
        // 중간 위치의 값이 키 값보다 작을 경우
        // 범위를 좁히기 위해선 하한선(start)를 올려야 한다.
        if (arr[mid] < key) {
            start = mid + 1;
        }
        // 중간 위치의 값이 키 값과 같거나 클 경우
        // 범위를 좁히기 위해선 상한선(end)을 내려야 한다.
        // 같을 경우의 인덱스도 포함하기에 "이상"인 것이다.
        else { // key <= arr[mid]
            end = mid;
        }
    }
    return end;
}