이진 탐색 - Upper Bound와 Lower Bound

이진 탐색

이진 탐색은 정렬된 상태의 데이터에서 원하는 값을 찾아내는 알고리즘이다.
데이터의 중앙값과 찾고자 하는 값을 비교한다.

이진 탐색은 탐색 대상이 매번 절반으로 줄어들기 때문에 시간 복잡도는 O(logN)이다.

 

이진 탐색의 동작 원리는 다음과 같다.

1. 배열이나 리스트를 정렬한다.
2. 배열이나 리스트의 중간 값을 선택한다.
3. 중간 값이 목표 값보다 크면 왼쪽 절반을 탐색하고, 중간 값이 목표 값보다 크면 오른쪽 절반을 탐색한다.
4. 중간 값과 목표 값이 같을 때까지 탐색한다.

예를 들어보자

정렬된 배열(arr) : [1, 3, 5, 7, 9, 11, 13]

목표 값 : 9

먼저 left는 0, right는 6로 시작한다.(시작 인덱스0, 가장 끝 인덱스 6)

public class BinarySearchMain {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int v = 7;
        int ans = binarySearch(arr, v);
        System.out.println(ans);
    }

    private static int binarySearch(int[] arr, int v) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] > v) {
                right = mid - 1;
            }
            else if (arr[mid] < v){
                left = mid + 1;
            }
            else return mid;
        }

        return -1;
    }
}

1. left = 0, right = 6이므로 mid = 3이다. arr[mid]는 arr[3] = 7이다. 목표 값인 9는 7보다 크므로 mid를 중심으로 오른쪽 절반을 다시 탐색한다. 즉 left 값을 mid + 1로 해준다.
2. left = 4, right = 6이므로 mid = 5이다. arr[mid]는 arr[5] = 9이다. 목표 값이 9와 동일하므로 else문에 들어와서 mid를 리턴해준다.
3. 만약 left <= right일 때까지, 즉, 시작점이 끝점보다 작거나 같을 때까지 탐색했을 때 원하는 값의 인덱스를 찾지 못하면 -1을 리턴해준다.

 

Upper Bound와 Lower Bound

이진 탐색의 방식으로 상한선과 하한선 방식이다.

 

Upper Bound는 상한선 방식으로 주어진 값보다 큰 값이 처음으로 등장하는 위치를 찾는다.

Lower Bound는 하한선 방식으로 주어진 값보다 크거나 같은 값이 처음으로 등장하는 위치를 찾는다.

 

[1, 3, 3, 5, 7]의 배열 / 목표 값 3의 upper bound는 인덱스 3이다.(값은 5)

[1, 3, 3, 5, 7]의 배열 / 목표 값 3의 lower bound는 인덱스 1이다.(값은 맨 처음 나오는 3)

 

코드로 구현해보자

package BinarySearch;

public class UpperBound {
    public static void main(String[] args) {
       // 이분탐색은 기본적으로 정렬되어 있어야 함
       int[] arr = {1, 2, 3, 4, 5, 6, 6};
       System.out.println("upper bound : " + upperBound(arr, 5));
       System.out.println("lower bound : " + lowerBound(arr, 5));
    }

    // 특정 값을 초과하는 가장 처음에 나오는 위치
    // 상한선
    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) {
             left = mid + 1;
          }
          else {
             right = mid;
          }
       }
       return left;
    }

    // 특정 값 이상인 첫번째 위치(인덱스)
    // 하한선
    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) {
             left = mid + 1;
          }
          else {
             right = mid;
          }
       }
       return left;
    }
}

target 값이 5이면 upper bound는 5보다 큰 값인 6이 맨 처음 나오는 인덱스인 5를 반환한다.

target 값이 5이면 lower bound는 5보다 크거나 같은 값인 5가 처음 나오는 인덱스인 4를 반환한다.

 

두 가지를 짚고 넘어가볼 수 있다.

1. 둘 다 right 값을 arr.length - 1이 아닌 arr.length로 하고 있다. 만약 upperBound(7)과 lowerBound(7)를 호출하게 되면 주어진 배열 크기만큼 리턴되어야 한다.(upper bound는 목표 값보다 큰 첫 번째 위치를 가리키므로 배열 끝 이후를 가리키게 되고, lower bound는 목표 값이 처음 나타나는 위치를 넘어서 배열 끝을 가리킨다.) 즉, 값이 없는 경우에도 올바를 결과를 리턴한다.
2. 이 때 left 값을 반환하는 이유는 탐색 과정에서 left가 최종적으로 특정 조건을 만족하는 지점을 가리키기 때문이다.그래서 최종적으로 left는 조건을 만족하는 최초의 위치를 가리키게 된다. 이진 탐색 과정에서 left는 항상 조건을 만족할 가능성이 있는 최소 인덱스를 유지한다.