[Algorithm] 이분탐색 알고리즘 - Upper Bound/Lower Bound

안녕하세요.

오늘은 이분 탐색 알고리즘에 대해 알아보겠습니다.

 

또한 탐색의 경계가 되는 Upper Bound와 Lower Bound에 대해 설명하고,

이분탐색의 탐색 범위에 관한 얘기도 해보겠습니다.

 

 

 

 

이분탐색이란?

정렬된 배열에서, 원하는 값을 효율적으로 찾는 알고리즘입니다.

배열의 중간값이 찾고자하는 값보다 크면 오른쪽을, 작으면 왼쪽을 버려 원하는 값을 찾습니다.

동작 과정은 다음과 같습니다.

 

1. left = 0, right = arr.length

2. 왼쪽을 버리면 left = mid+1로, 오른쪽을 버리면 right = mid로 업데이트 합니다.

3. 하한값 탐색 시, mid >= taret일 때만 버립니다.

4. 상한값 탐색 시, mid > target일 때만 버립니다.

5. 배열 탐색은 left < right 일 때까지만 진행합니다.

6. left값을 리턴합니다.

 

 

 

 

Upper Bound(상한선)

찾고자 하는 값을 초과하는 값이 처음 등장하는 위치를 반환합니다.

 

예) 1을 찾고자 할 때 : 1-1-2-3, 0-0-2-3

 

     간단하게 자바로 구현한 코드는 다음과 같습니다.

public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = (left + right) / 2;
        
        // 목표값을 초과할 때만 오른쪽 버리기
        if (arr[mid] > target) {
            right = mid;
        } else { // 같을 때는 왼쪽 버리기
            left = mid + 1;
        }
    }
    return left;
}

 

 

 

 

 

 

 

Lower Bound(하한선)

찾고자 하는 값 이상(= 같은 값 포함)이 처음 등장하는 위치를 반환합니다

 

예) 1을 찾고자 할 때, 1-1-2-3 이라면 첫번째 1을 반환합니다.

 

     3-1-1-2-3과 같은 경우에선 3을 반환하여 오류가 생기는 것이 아닐까 고민했습니다.

     하지만 이분 탐색은 항상 정렬된 배열에 대해서 수행하기 때문에 위와 같은 경우는 고려하지 않아도 됩니다.

 

     간단하게 java로 구현한 코드는 다음과 같습니다.

public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length; // 반닫힌구간

    while (left < right) {
        int mid = (left + right) / 2;
        
        // 목표값 이상일 때 오른쪽 버리기
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

 

 

 

 

 

 

이분 탐색의 탐색범위는 반닫힌구간 [left, right)

이분 탐색으로 탐색 시, 반닫힌 구간 [left, right)을 사용해야 합니다.

이에 관한 많은 설명을 읽었으나,, 이해하지 못해 그냥 외우기로 했습니다..

 

자세한 설명을 원한다면 아래 글을 참조하시면 좋을 것 같습니다.

이분탐색은 반닫힌구간을 써야하는 이유

 

 

 

 

 

 

 

이분 탐색을 이용하여 특정값 포함 여부 찾기

// 이분탐색은 항상 반열린 구간으로 탐색하므로, binarySearch(target, 0, n)으로 시작한다.

static boolean binarySearch(int target, int left, int right) {
    while (left < right) { // 구간이 존재하는 동안 반복
        int mid = (left + right) / 2;

        if (arr[mid] == target) return true;

        if (arr[mid] > target) {
            right = mid; // 왼쪽 구간, mid 제외
        } else {
            left = mid + 1; // 오른쪽 구간, mid 제외
        }
    }
    
    return false; // 더 이상 구간이 없으면 false
}

 

 

 

 

정리

이분 탐색은 중간값을 기준으로 잡습니다.

중간값이 목표값보다 작다면 왼쪽을 버리고(left = mid + 1), 중간값이 크다면 오른쪽을 버리며(right = mid) 탐색합니다.

Upper Bound는, 목표값을 초과하는 처음 위치를 반환합니다. (목표 + 1의 인덱스)

Lower Bound는, 목표값 이상인 처음 위치를 반환합니다. (목표의 인덱스)

항상 반닫힌 구간에 대해 수행해야합니다. [left, right)