[알고리즘] Binary Search : lower bound & upper bound

Binary Search : lower bound & upper bound

Binary Search (이진 탐색)

이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다. 기준 값을 구해서 그 값을 기준으로 데이터를 나눠서 검색하는 방법이다. 특정 값을 찾을 때는 기본 이진 탐색으로 쉽게 구할 수 있다. 하지만 중복된 데이터에서 탐색할 때는 조금 더 응용된 방법을 사용해야한다. (예를 들어, 중복 된 데이터에서 특정 데이터가 몇 개가 존재하는지 등) 따라서 lower bound와 upper bound를 구해야한다.

• Lower bound는 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해준다.
• High Bound는 특정 값보다 처음으로 큰 값이나 나오는 위치를 리턴해준다.

• 위의 그림을 보면 찾고자 하는 값이 3일 경우, lowerBound(3)를 호출하면 3보다 같거나 큰 값이 처음 나오는 위치인 인덱스 3을 리턴하고, upperBound(3)을 호출하면 3보다 처음으로 나오는 큰 값인(4)의 위치인 인덱스 6을 리턴해준다.

코드

• Lower bound

  • lower bound 는 큰 값이 처음 나오는 것을 리턴해야하기 때문에 만약 존재하지 않는 큰 수가 있는 경우, high = data.length-1로 하면 배열의 마지막 인덱스를 넘겨주게 된다. 따라서 high = data.length로 해야한다.

  • 기본 이진탐색과 다른 점은 값을 찾았을 때 바로 리턴하는 것이 아니라 처음으로 나오는 값을 찾기 위해 범위를 좁혀가면서 찾는다. 그래서 high = mid로 하고 범위를 좁혀가는 것이다.

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

• Upper bound

  • lower bound와 거의 동일하다. 단지 최초로 큰 값이 나오는 곳을 찾기위해 범위를 좁혀간다.

  • 계속 헷갈리는 부분은 Upper bound는 찾고자하는 마지막 값의 인덱스를 찾는 것이 아니라는 점이다.

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

• 이미지 출처 : http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html