Binary Search, 이진탐색

정렬된 배열에서 특정 값의 위치 찾기

아래의 정렬된 배열에서 6을 찾는다고 하자.

----------
0123456789

지금은 배열 전체가 탐색 범위이다. 여기서 중앙에 있는 값과 목표로 하는 값(6)을 비교해 보자. 중앙에 있는 값은 index가 4인 값이다. floor((0 + 9)/2) = floor(4.5) = 4, arr[4] < target 임으로 index가 0~4인 값들은 target보다 작기 때문에 확인해 보지 않아도 된다.

xxxxx-----
0123456789

이제 탐색 범위는 index가 5~9인 값들이다. 이 범위에서 중앙에 있는 값과 목표로 하는 값을 비교해 보자. 중앙에 있는 값은 index가 7인 값이다. (5 + 9) / 2 = 7, arr[7] > target 임으로 index가 7~9인 값은 target보다 크기 때문에 확인하지 않아도 된다.

xxxxx--xxx
0123456789

같은 방법을 수행하면 탐색 범위는 또 줄어든다.

xxxxxx-xxx
0123456789

4번 만에 6을 찾은 것을 볼 수 있다. 위 과정을 수행하는 이진탐색 알고리즘을 아래의 코드로 구현할 수 있다.

int search(vector<int>& arr,int target){
    int l = 0;
    int r = arr.size()-1;
    int mid;

    while(l <= r){
        mid = l + (r-l)/2;
        if(arr[mid]==target) return mid;
        else if(arr[mid] < target) l = mid+1;
        else r = mid-1;
    }
    return -1;
}

lower_bound

배열의 값들이 어떤 조건 condition을 만족하는지의 여부를 알 수 있고, 확인해 보았더니 아래와 같은 꼴인 것을 보았다고 하자.

// T는 condition을 만족함
// F는 condition을 만족하지 않음
0123456789
------V---
FFFFFFTTTT

특정 위치를 기준으로 왼쪽의 값들은 condition을 만족하지 않고, 오른쪽의 값들은 모두 만족할 때 condition을 만족하는 값 중 가장 왼쪽에 있는 값의 index를 알고 싶다. 이도 이진탐색을 이용하여 O(logn)에 구할 수 있다.

알고리즘을 먼저 보자.

int lowerbound(vector<int>& arr){
    int l = 0;
    int r = arr.size();
    int mid;

    while(l < r){
        mid = l + (r-l)/2;
        if(condition(arr[mid])) r = mid;
        else l = mid+1;
    }
    return l;
}

특정 값의 위치를 찾을 때와 달라진 점을 보자.

우선 r의 기본값이 달라졌다. 초기 l, r는 반환할 값의 가능한 범위를 표현하여야 한다. 만약 배열값이 모두 condition을 만족하는 경우 반환해야 할 값은 0이되며 어느 값도 condition을 만족하지 않으면 arr.size()를 반환해야 한다.

// 모든 값이 만족하는 경우 반환해야 할 위치
V---
TTTT

// 어느 값도 만족하지 않는 경우 반환해야 할 위치
----V
FFFF

반복문의 종료 조건도 달라졌는데, 이는 반복문을 빠져나오면 l=r 이 되도록 한다.

r의 값을 수정할 때 mid-1이 아닌 mid이다. 이는 mid 값이 경계에 있는 값일 때 탐색 범위에서 벗어나는 것을 막기 위함이다.

// r = mid - 1로 업데이트할 때
012345    012345
L-M--R => LR----
FFTTT  => FFTTT

// r = mid로 업데이트할 때
012345    012345
L-M--R => L-R---
FFTTT  => FFTTT

이제 위 알고리즘으로 아래 배열에서 condition이 T인 값 중 가장 작은 index를 찾아보자.

0123456789
L----M----R
FFFFFFTTTT

처음 탐색 범위가 배열 전체일 때 중앙의 값(index = 5)을 확인하였더니 F이다. index 5보다 왼쪽에 있는 값들은 모두 F일 테니 index 0~5의 범위를 탐색 범위에서 제외한다.

0123456789
xxxxxxL-M-R
FFFFFFTTTT

index 8을 확인하였더니 T이다. index가 8 이상이면 값이 T임으로 index가 8+1부터 끝까지의 범위를 탐색 범위에서 제외한다.

0123456789
      M
xxxxxxLRxx
FFFFFFTTTT

index 6을 확인하였더니 T이다. r = mid를 수행하면 l = r = 6이 되고, !(l < r)이기 때문에 반복문을 벗어난다.

0123456789
      L
xxxxxxRxxx
FFFFFFTTTT

성공적으로 condition을 만족하는 가장 작은 index를 찾았다.

문제를 풀 때 이 condition을 잘 디자인하는 것이 중요하다.

upper_bound

lower_bound와 반대로 배열의 값들이 condition을 만족하는지의 여부가 아래와 같을 때 (condition을 만족하는 가장 큰 index + 1)을 구하고자 한다.

0123456789
------V---
TTTTTTFFFF

T인 가장 오른쪽 index가 아닌 그 index + 1 임에 유의하여야 한다. 이 점은 STL의 upper_bound를 사용할 때도 동일하다.

위와 같이 조건을 따져가며 코드를 작성하여도 되는데, 위의 lower_bound에서 약간의 코드 변경만으로도 구현할 수 있다

condition을 만족하는지의 여부가 아닌 !condition을 만족하는지를 확인하자. 이 경우 위 배열에서 !condition 만족 여부는 아래와 같다.

0123456789
------V---
FFFFFFTTTT

!condition을 만족하는지의 lower_bound를 찾는 문제와 동일하다는 것을 볼 수 있다.

따라서 코드는 아래와 같이 짤 수 있다.

int upperbound(vector<int>& arr){
    int l = 0;
    int r = arr.size();
    int mid;

    while(l < r){
        mid = l + (r-l)/2;
        if(!condition(arr[mid])) r = mid;
        else l = mid+1;
    }
    return l;
}

정렬된 배열에서 특정 값의 개수 구하기

정렬된 배열에서 어떤 수 target의 개수를 구하고자 한다. 이 경우 arr[i] <= target을 만족하는 upper bound에서 target <= arr[i]를 만족하는 lower bound를 빼면 된다.

아래 배열에서 3의 개수를 구하여 보자.

// L : Lower bound of 3 <= arr[i]
// U : Upper bound of arr[i] <= 3
--L---U--
113333446

L = 2이고 U = 6이다. U-L = 4 임으로 3은 4개 있다.

동일한 배열에서 5의 개수를 구하여 보자

// L : Lower bound of 5 <= arr[i]
// U : Upper bound of arr[i] <= 5

        U
--------L
113333446

L=U=8 임으로 U-L=0이다. 5는 배열에 0개 존재한다.

코드로는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

int lowerbound(vector<int>& arr,int target){
    int l = 0;
    int r = arr.size();
    int mid;

    while(l < r){
        mid = l + (r-l)/2;
        if(target <= arr[mid]) r = mid;
        else l = mid+1;
    }
    return l;
}

int upperbound(vector<int>& arr, int target){
    int l = 0;
    int r = arr.size();
    int mid;

    while(l < r){
        mid = l + (r-l)/2;
        if(!(arr[mid] <= target)) r = mid;
        else l = mid+1;
    }
    return l;
}

int main(void){
    vector<int> arr{1,1,3,3,3,3,4,4,6};

    // count 3 ,result = 4
    cout << upperbound(arr,3) - lowerbound(arr,3) << endl;

    // count 5, result = 0
    cout << upperbound(arr,5) - lowerbound(arr,5) << endl;
    return 0;
}

Cpp STL algorithm에서 binary_search 가져다 쓰기

CPP에서는 algorithm을 include 하면 이미 만들어진 binary_search, upper_bound, lower_bound를 사용할 수 있다.

• binary_search는 주어진 값이 정렬된 배열 내에 존재하는지 여부를 bool type으로 반환한다.
• lower_bound는 정렬된 배열에서 target <= arr[i]인 가장 작은 i의 위치에 해당하는 iterator를 반환한다.
• upper_bound는 정렬된 배열에서 target < arr[i]인 가장 작은 i의 위치에 해당하는 iterator를 반환한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(void) {
    vector<int> arr{ 1,1,3,3,3,3,4,4,6 };

    // binary search, result = 1
    cout << binary_search(arr.begin(), arr.end(), 4) << endl;

    // lower bound, result = 2
    cout << lower_bound(arr.begin(), arr.end(), 3) - arr.begin() << endl;

    // upper bound, result = 6
    cout << upper_bound(arr.begin(), arr.end(), 3) - arr.begin() << endl;

    return 0;
}

Python의 bisect에서 가져다 쓰기

Python의 bisect 모듈에는 이미 정렬된 리스트에 값을 삽입할 때 삽입 후 다시 정렬하는 일을 하지 않도록 처음부터 삽입해야 하는 위치를 알려주는 함수들이 존재한다. 우리가 값의 개수를 구하기 위해 작성한 lowerbound, upperbound와 Cpp STL의 lower_bound, upper_bound의 python 버전이다.

from bisect import bisect_left, bisect_right

arr = [1,1,3,3,3,3,4,6]

print(bisect_left(arr,3)) # 2
print(bisect_right(arr,3)) # 6