Lower Bound & Upper Bound

이진탐색(Binary Search)

• 자료구조의 종류 : 선형(Array & List..)과 비선형(Tree & Graph..)

• 이진탐색은 선형 구조의 탐색 방법 중 하나

• 분할 정복 방식으로 수행

  순차 탐색의 경우 O(n) BUT 이분 탐색의 경우 O(logn)

  정렬된 경우 효율적으로 탐색이 가능

• 이분 탐색 방법(1~100중 15 찾기)

  1) 1~100의 중간값인 50인지 물어본다. (작다)
  2) 1~50의 중간값인 25인지 물어본다. (작다)
  3) 1~25의 중간값인 12인지 물어본다. (크다)
  4) 12~25의 중간값인 18인지 물어본다. (작다)
  5) 12~18의 중간값인 15인지 물어본다. (o)

Lower Bound(이상)

• 이진 탐색은 정확히 같은 값을 찾는 것에 비해 Lower Bound는 주어진 인자 값보다 작거나 큰 값이 처음으로 나올 때 Return

• 이진 탐색을 하며 인자 값과 같은 값이 나와도 처음으로 같은 값을 찾기 위해 지속해서 범위를 좁혀 가며 탐색

• JAVA 코드

public int lowerBound(int[] array,  int value) {
        int low = 0;
        int high = array.length;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (value <= array[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

Upper Bound(초과)

• Lower Bound와 마찬가지의 방식이지만 Upper Bound의 경우 인자 값보다 큰 첫번째 위치를 반환한다.

• 크게 알고리즘이 변하지는 않는다. 찾아야 할 값과 같을 때 Lower Bound에서는 범위를 값이 작은 방향으로 좁힌다면, Upper Bound의 경우에는 큰 값의 방향으로 범위를 좁힌다.

• JAVA 코드

public int upperBound(int[] array, int value) {
        int low = 0;
        int high = array.length;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (value >= array[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }