이진탐색과 lower/upper Bound

이진 탐색

이진 탐색이란 주어진 데이터에서 원하는 값을 찾을 때, 데이터를 절반씩 나누어가며 탐색하는 방법이다.

간단한 예시를 통해 이진 탐색에 대해 알아보자.

다음과 같은 데이터가 주어져있을 때, 내가 찾고 싶은 값이 11이라고 해보자.

이진 탐색은 앞서 데이터를 절반씩 나누어가며 탐색하는 방법이라고 언급했었다.

따라서, 이진 탐색을 시작하기 전 준비 단계는 다음과 같다.

1. 가장 작은 값(left), 가장 큰 값(right)을 가리키기
2. 중간값(mid)을 찾기 (mid = (left + right) / 2)

이진 탐색이 진행되었다면 1. 단계는 left와 right를 알맞은 위치에 옮기기로 변경된다.

여기서 left, right, mid는 모두 배열의 인덱스를 나타낸다.

1 (left)

11 (target)

13 (mid)

44 (right)

준비 단계가 끝났다면, 비교 단계를 시작한다. 여기서 target은 찾으려고 하는 값을 나타낸다.

1. data[mid] < target

타겟보다 데이터의 중간값이 더 작다면, 
타겟은 데이터의 중간값의 우측에 위치해있다는 것을 나타내기 때문에 
중간값을 포함한 좌측 값들은 검색 범위에서 제외한다. 
따라서 좌측 끝을 나타내는 left를 mid+1로 옮긴다.


2. target < data[mid]

타겟이 데이터의 중간값보다 더 작다면, 
타겟은 데이터의 중간값의 좌측에 위치해있다는 것을 나타내기 때문에 
중간값을 포함한 우측 값들은 검색 범위에서 제외한다. 
따라서 우측 끝을 나타내는 right를 mid-1로 옮긴다.


3. target == data[mid]

발견!

우리는 위 3가지의 비교 단계 중, 현 상황에 알맞은 것을 적용하여 계속 검색 범위를 줄여나가면 된다.

1 (left)

11 (target)

13 (mid)

44 (right)

우리의 예시에서는 위 3가지의 비교 단계 중, 2번에 속하므로(11 < 13), rigth를 mid - 1로 옮긴다.

1 (left)

11 (target, right)

다시 준비 단계에 들어간다.

left와 right는 옮겼으므로, mid를 다시 설정하자.

mid = (left + right) / 2이기 때문에, 1임을 알 수 있다.

1 (left)

11 (target, right, mid)

다시 비교 단계에 들어간다.

현 상황에 적합한 비교 단계는 3번, target == mid인 경우이므로, 우리는 원하는 값을 찾았다.

이렇게 준비 단계와 비교 단계를 반복해나가며 우리가 원하는 값을 찾는 것을 이진 탐색이라고 한다.

이진 탐색을 하기 위해서는 중요한 전제 조건이 있는데, 바로 데이터가 정렬된 값이어야한다는 점이다. 앞서 비교 단계에서 1, 2의 경우 중간값과 타겟을 비교하여 사용되지 않는 범위는 아예 배제시켜버리기 때문에, 데이터가 정렬되어있어야만 사용할 수 있다.

이진 탐색을 자바 코드로 나타내면 다음과 같다.

int[] data = new int[]{1, 11, 13, 25, 31, 44};

int left = 0;
int right = data.length - 1;
int findValue = 11;

while (left <= right) {
    int mid = (left + right) / 2;
    int target = data[mid];
    
    if (findValue < target) {
        right = mid - 1;
    } else if (target < findValue) {
        left = mid + 1;
    } else {
        return mid;
    }
}

이진 탐색을 활용하면, 효과적으로 lowerBound와 upperBound를 구할 수 있다.

Lower Bound

lowerBound란, 특정 K값과 같거나 큰 값이 가장 처음으로 나오는 값의 위치를 말한다.

lower bound를 구하는 방법과 이진 탐색과의 차이점은 이진탐색은 찾으려고 하는 값과 정확히 같은 값이 있는 위치를 찾는 것이 목표이지만, lower bound는 주어진 값보다 같거나 큰 값이 처음으로 나오는 값의 위치를 리턴해야하는 것이 목표이다.

따라서 주어진 데이터가 {1,2,3} 인 경우 lowerBound(4)을 구할 때, 주어진 데이터 중 4의 lowerBound는 존재하지 않으므로 주어진 데이터의 크기만큼 리턴되어야한다. 따라서 right를 array.length로 지정해주어야한다.

또한 target < array[mid]인 경우 이진 탐색에서는 right = mid-1로 옮겨주었었는데, {1,2,3,3,3}과 같은 경우 3의 lowerBound는 첫번째로 등장하는 3의 위치인 2가 반환되어야하기 때문에 right = mid로 지정하여 범위를 좀 더 좁히며 찾아야한다.

int left = 0;
int right = array.length;

while (left < right) {
    int mid = (left + right) / 2;
    if (findValue <= array[mid]) { // lowerBound의 후보인 경우
        right = mid;
    } else {
        left = mid + 1;
    }
}

return right;

Upper Bound

upperBound란, 특정 K값보다 처음으로 큰 값이 나오는 위치를 말한다. upperBound 코드 또한 lowerBound와 마찬가지로 배열의 길이만큼이 리턴될 수 있기 때문에 right = array.length로 지정해주어야하며, 탐색한 값이 주어진 값보다 크다면 바로 리턴하지 않고 처음으로 큰 값을 찾기 위해 right = mid로 지정해 범위를 좁히면서 찾아간다.

int left = 0;
int right = array.length;

while (left < right) {
    int mid = (left+right)/2;
    if (array[mid] <= value) {
        left = mid + 1;
    } else {
        right = mid;
    }
}

return right;

참고 자료

저작자표시

이진탐색과 lower/upper Bound

목차

이진 탐색

Lower Bound

Upper Bound

티스토리툴바