이진탐색-상/하한선((lower bound,upper bound)

주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터내에 특정 값이 존재하는지 검색하는 방법 중  이진탐색(Binary Search)은 자료를 정렬한후 분할정복방식으로 데이터를 2/1씩 나누면서 값이 존재하는지 확인하는 알고리즘을 사용했었다.

 

이진탐색이 데이터내 특정 값을 정확히 찾는 것이라면 lower bound와 upper bound 는 이진탐색 알고리즘에서 약간 변형된 것으로 중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘으로

lower bound는 데이터내 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴해주고 upper bound 는 K값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘이다.

 

 

 △ [출처] http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

위 그림에 보이듯이 중복된 값( 2, 3 값이 여러개 있다)이 있는 배열을 정렬한 상태에서  3의 값을 기준으로 

lower_bound(3) 를 호출하면  3보다 같으면서 큰 값이 최초로 나타나는 index = 3을 리턴해주고 

upper_bound(3) 3보다 큰 값이 젤 처음 나오는 index = 6을 리턴한다. 

 

다음 예제를 보면 lower_bound 와 upper_bound 가 어떻게 다른지 좀 더 명확해 질 것이다.

 

 △ [출처] http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

 

lower_bound 와 upper_bound 는 stl 에서 내장된 메소드로 제공해주지만 자바에서는 제공해 주지 않기 때문에 필요하다면 직접 구현을 해야한다.

구현은 이진탐색(Binary Search)과 거의 비슷해서 어렵지 않으나 약간 다른 부분이 있어 그 부분만 주의 깊게 살펴보면 된다.

구현 전에 우선 이진검색 코드를 다시 상기하자

 

public static  int binarySearch(int[] list, int key) {
        // 맨처음 low = 0, high는 배열의 끝이다.
        int low = 0;
        int high = list.length - 1;
 
        while (low <= high) {
            int mid = low + (high - low)/2; // mid 값을 계산.
 
            if (key > list[mid]) // 키값이 더 크면 왼쪽을 버린다.
                low = mid + 1;
            else if (key < list[mid]) // 키값이 더 작으면 오른쪽을 버린다.
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }
 

 

lower bound algorithm

이진탐색과 다른점은 크기가 9인  int test1[] = {1,2,2,3,3,3,4,6,7} 이 주어질때 이진탐색은 정확히 같은 값이 있는곳을 찾는거지만 lower bound는 주어진 값보다 같거나 큰 값이 처음으로 나오는걸 리턴해야 하는데 만약 lower_bound(9) 면 주어진 배열크기 만큼 리턴되어야 하기 때문에 high = array.length -1 이 아니고 high = array.length로 지정 해야 한다. 
그리고 탐색한 값이  주어진 값보다 크거나 같으면 바로 리턴하지 같거나 처음으로 나오는 값을 찾기위해 범위를 더 좁히면서 찾아간다. 
예를들어 test1 에서 lower_bound(3) 을 호출하면 
{1,2,2,3, 3 <- array[mid]는 여기를 가리킴.,3,4,6,7}
하지만 우리가 찾으려 하는 index 는 처음 mid = 4 가 아닌  mid=3 이어야 한다.
따라서 크거나 같은경우 high = mid 로 지정해서 범위를 좀더 좁혀 나가면서 찾아가는 것이다. 

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

 

upper bound algorithm

lower bound와 마찬가지로 upper bound는 주어진 값보다  큰 값이 처음으로 나오는걸 리턴해야 하는데 만약 upper_bound(9) 면 주어진 배열크기 만큼 리턴되어야 하기 때문에 high = array.length -1 이 아니고 high = array.length로 지정 해야 한다. 
그리고 탐색한 값이 주어진 값보다 크다면  바로 리턴하지 않고 최초로 큰 값이 있는 위치를  찾기 위해 high = mid 지정하여 범위를 더 좁히면서 찾아가면 된다. 

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

 

public class Main {
 
    public static void main(String[] args)  {
 
        int test1[] = {1,2,2,3,3,3,4,6,7};
        Assert.check(lowerBound(test1, 4) == 6);
        Assert.check(upperBound(test1, 4) == 7);
 
        Assert.check(lowerBound(test1, 3) == 3);
        Assert.check(upperBound(test1, 3) == 6);
 
        Assert.check(lowerBound(test1, 5) == 7);
        Assert.check(upperBound(test1, 5) == 7);
 
        Assert.check(lowerBound(test1, 8) == 9);
        Assert.check(upperBound(test1, 8) == 9);
 
        Assert.check(lowerBound(test1, 0) == 0);
        Assert.check(upperBound(test1, 0) == 0);
 
 
    }
}