블로그 이사 중입니다 >> gumgood.github.io

Binary search algorithm - detail 본문

Problem Solving/분류없음

Binary search algorithm - detail

gumgood 2019. 4. 4. 12:24

Binary Search(이분 탐색)는 일반적으로 간단한 알고리즘에 속한다. 막상 문제를 풀다보면 'exit conditions'나 'midpoint calculation'에 있어서 헷갈릴 여지가 있다. 풀려는 문제의 조건에 따라 미묘한 구현의 차이가 존재하기 때문이다. 이를 명확하게 정리해두고자한다.

Algorithm

Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value.

 - If the target value matches the middle element, its position in the array is return.

 - If the target value is less than the middle element, the search continues in the lower half of the array.

 - If the target value is greater than the middle element, the search continues in the upper half of the array.

By doing this, the algorithm eliminates the half in which the target value connot lie in each interation.

Procedure

Given an array\(A\) of \(n\) elements with values or records \(A_0, A_1, A_2, ..., A_{n-1}\) sorted such that \(A_0 \le A_1 \le A_2 \le ... \le A_{n-1}\), and the target value \(T\), the following subroutine uses binary search to find the index of \(T\) in \(A\).

 

    1. Set \(L=0\) and \(R=n-1\)
    2. If \(L > R\), the search terminates as unsuccessful.
    3. Set \(m\) (the position of the middle element) to the floor of \(L+R \over 2\) (\(\lfloor {L+R \over 2} \rfloor\)), which is the greatest integer less than or equal to \(L+R \over 2\)
    4. If \(A_m < T\), set \(L=m+1\) and go to step 2.
    5. If \(A_m > T\), set \(R=m-1\) and go to step 2.
    6. Now \(A_m = T\), the search is done; return \(m\).

 

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

다른 구현

위의 procedure에서 target value를 찾으면 loop를 끝내는 것과 달리, 한 원소만 남을 때까지 범위를 줄이고 그 원소가 target value와 일치하는지를 확인하는 방법도 있다. 이는 각 반복문 당 수행되는 조건 연산자가 줄어들어 더 빠른 수행 속도를 기대할 수 있다. 그러나 반복문 횟수 자체가 늘어나는 점도 고려해야 한다.

 

    1. Set \(L=0\) and \(R=n-1\)
    2. If \(L = R\), go to step 6
    3. Set \(m\) (the position of the middle element) to the ceiling of \(L+R \over 2\) \((\lceil {L+R \over 2} \rceil)\), which is the least integer greater than or equal to \(L+R \over 2\)
    4. If \(A_m > T\), set \(R=m-1\) and go to step 2.

    5. set \(L=m\) and go to step 2.
    6. Now \(A_m = T\) the search is done; return \(m\).

 

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L < R:
        m := ceiling((L + R) / 2)
        if A[m] > T:
            R := m - 1
        else:
            L := m
    if A[L] == T:
    	return L
    return unsuccessful

Time Complexity

Binary search의 시간 복잡도는 다음과 같이 쓸 수 있다.

 

\( T(n)=T(n/2)+c \)

 

이 recurrence를 Tree method나 Master method로 풀면

 

\( \Theta(logn) \)

 

binary search는 정렬된 배열에서 수행할 때를 가정하고 만들어졌다. 정렬되지 않은 경우 최소 \(O(nlogn)\)동안 정렬을 먼저 수행해야 한다. 단순한 접근법인 linear search algorithm의 시간복잡도가 \(O(n)\)임을 고려했을 때, query 개수나 다른 조건을 고려해서 적절히 선택해야 한다.

 

Auxiliary Space는 Original input을 저장하는 메모리를 제외하고 쓰이는 모든 메모리의 공간의 크기를 뜻한다. input size는 \(O(n)\)을 반드시 추가로 필요한 공간이 이보다 작은 경우 space complexity로 논하기 어렵기 때문이다.

위의 procedure들의 경우는 \(O(1)\)의 크기를 차지한다.

reursion으로 binary_search를 구현할 수도 있는데 이 경우 \(O(logn)\)의 call stack space를 차지한다.

응용


Duplicate elements

중복된 원소가 있어도 target value의 존재성을 확인하는 작업하는데는 아무런 상관이 없다. 그러나 leftmost element나 rightmost element의 위치를 요구하는 경우에는 명확하게 수행하는 procedure가 필요하다.

 

To find the leftmost element, the following precedure can be used:

    1. Set \(L=0\) and \(R=n\).

    2. If \(L \ge R\), go to step 6.

    3. Set \(m = {\lfloor {L+R \over 2} \rfloor}\).

    4. If \(A_m \lt T\), set \(L=m+1\), and go to step 2.

    5. Otherwise, if \(A_m \ge T\), set \(R=m\), and go to step 2.

    6. Now \(L=R\), the search is done, return L.

\(L<n\) and \(A_L=T\)이면, \(A_L\)은 \(T\)값을 갖는 leftmost element이다.

\(T\) 값의 원소가 없더라도, \(L\)은 \(A\)에서 \(T\)보다 작은 원소의 수와 같다.

 

function binary_search(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

* lower bound를 찾는 동작과 동일하다

 

To find the rightmost element, the following procedure can be used:

    1. Set \(L=0\) and \(R=n\)

    2. If \(L \ge R\), go to step 6.

    3. Set \(m = {\lfloor {L+R \over 2} \rfloor}\)

    4. If \(A_m \le T\), set \(L=m+1\), and go to step 2.

    5. Otherwise, if \(A_m \gt T\), set \(R=m\), and go to step 2.

    6. Now \(L=R\), the search is done, return \(L-1\).

\(L>0\) and \(A_{L-1}=T\)이면 \(A_{L-1}\)는 \(T\)값을 갖는 rightmost element이다.

\(T\)값의 원소가 없더라도, \(n-L\)은 \(A\)에서 \(T\)보다 큰 원소의 갯수와 같다.

 

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] <= T:
            L := m + 1 
        else:
            R := m
    return L - 1

 

* upper bound의 index (\(L\))를 찾고 right most element (\(L-1\)) 를 return한다.

upper bound는 target value보다 큰 값을 갖는 element들 중 가장 앞의 index를 가르킨다.

Approximate matches

binary search algorithm로 leftmost/rightmost element를 구하는 procedure로 유사한 값들을 계산해낼수 있다. Rank(the number of smaller elements), Predecessor(next-smaller elements), Successor(next-largest element), Nearest neighbor, Range queries 등을 해결 할 수 있다.

  - Rank query는 leftmost element를 찾는 procedure와 동치이다.

  - Predecessor query는 rank query값이 \(r\)일 때, \(r-1\)이다.

  - Successor query는 rightmost element를 찾는 procedure 값이 \(r\)일 때, \(r+1\)이다.

  - The nearest neightbor는 predecesoor나 successor 중 더 가까운 값이다.

  - Range query는 두 값(\(A, B\))가 주어졌을 때, 그 사이값(\(A \le x \lt B\))을 가지는 원소들의 갯수를 요구한다. 각 경계값 \(A\), \(B\)보다 작은 원소의 수를 알면 쉽게 구할 수 있다.

 

Variations


Uniform binary search

일반적인 binary search와 거의 동일하다. binary search에서 반복문을 돌 때마다 아래의 연산으로 mid point를 계산한다.

mid = floor((L + R) / 2)

이 연산을 줄여서 optimize하는 방법이다.

\(a[i]\)를 검사 했을 때, 다음 비교할 대상은 \(a[i+2^p]\) 또는 \(a[i-2^p]\)이다. 다음 대상까지의 거리인 \(2^p\)를 미리 계산해 'Look-up' array에 저장한다. 다음 반복문으로 넘어갈 때 index에 \(2^p\)를 더하거나 빼기만 하면 되므로 더 빠르게 수행이 가능하다.

Look-Up array를 만드는 전처리에 드는 비용이 \(O(n)\)이므로 query가 매우 많은 경우 최적화에 유용하다.

Exponential search

binary search를 unbounded list로 확장할 수 있다. 간략히 설명하면, index를 2배로 늘려가면서 탐색해서 target value의 upper bound를 찾고 이 범위 안에서 binary search로 target value를 갖는 원소를 찾는 방법이다. 즉, range를 줄여나가는 binary search의 idea를 반대로 생각해서 upper bound를 exponentail하게 찾는 방법이다. 시간복잡도는 자명하게 \(O(logn)\)이다.

Interpolation search

mid point를 계산해서 비교해 나가는 것과는 다르게 범위 안에서 가장 큰 \(A[L]\)와 가장 작은 \(A[R]\) 그리고 \(T\)를 비교해서 "있을만한" 위치를 mid point로 정한다. index가 아닌 element들의 값을 비교해서 줄여나간다. 그래서 uniformly distruted array에서만 수행할 수 있다. 이 조건이 없으면 index와 element 값과의 관계가 거의 무관하기 때문에 적절한 mid ponit를 구할 수가 없다.

element들이 uniformly distributed 되었을 때, 시간복잡도는 \(O(loglogn)\)이다.

 

int mid = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));

Implementation

binary search, upper bound, lower bound를 C/C++로 구현해보자.

#include<cstdio>

int binarySearch(int a[],int n, int t){
    int l = 0, r = n-1;
    while(l <= r){
        int m = (l+r)/2;
        if(a[m] < t)
            l = m + 1;
        else if(a[m] > t)
            r = m - 1;
        else
            return m;
    }
    return -1; // fail
}

int lowerBound(int a[],int n,int t){
    int l = 0, r = n;
    while(l < r){
        int m = (l + r)/2; // floor
        if(a[m] < t)
            l = m + 1;
        else
            r = m;
    }
    return l;
}

int upperBound(int a[],int n,int t){
    int l = 0, r = n;
    while(l < r){
        int m = (l + r)/2; // floor
        if(a[m] <= t)
            l = m + 1;
        else
            r = m;
    } 
    return l;
}

int main(){
    int n = 10;
    int a[] = {1,2,2,4,4,4,4,6,6,7};
    
    printf("binary search return: %d\n", binarySearch(a, n, 4)); // 4
    printf("lower bound return: %d\n", lowerBound(a, n, 4)); // 3
    printf("uppder bound return: %d\n", upperBound(a, n, 4)); // 7

    printf("binary search return: %d\n", binarySearch(a, n, 5)); // -1
    printf("lower bound return: %d\n", lowerBound(a, n, 5)); // 7
    printf("uppder bound return: %d\n", upperBound(a, n, 5)); // 7

    return 0;
}

매 loop문이 시행되는 동안 고려하는 범위 \([l,r]\)를 탐색 범위라 하자. exit condition이 \(l \le r\)인 경우, 탐색 범위 \([l,r]\)의 크기가 0이 될 때까지 찾는다. 마지막 하나의 element도 condition statement를 거쳐야 한다. 반면 \(l \lt r\)인 경우, 범위 \([l,r]\)의 크기가 1이 될때까지 찾는다. 마지막 element의 조건에 관계 없이 return값을 가진다 (lower bound, upper bound).

lower bound와 upper bound는 탐색 범위를 반으로 줄여나가는 점은 동일하지만 중복된 target value의 element를 처리하는 부분에서 차이가 있다. 이를 살펴 보기 전에 mid point를 구하는 과정을 정리한다. mid point 계산에 floor function을 썼는데, mid point 후보 원소 두 개가 같은 value인 경우 왼쪽을 mid point로 고르게 된다. 따라서 같은 원소로 이뤄진 range에서는 왼쪽으로 범위가 좁혀나간다.

lower bound의 경우 target value들을 탐색 범위에 포함 시키면서 loop문을 진행한다. 결국 target value로 이뤄진 range에서 가장 왼쪽에서 끝난다. upper bound의 경우 target value들을 탐색 범위에서 제외하면서 loop문을 진행한다. target value를 포함하지 않으면서 가장 왼쪽에 있는 element를 찾게 되는데 이는 upper bound를 만족한다.

* target value가 있는 범위는 \([lower \ bound, upper \ bound)\)이다. 

 

 

참고 자료

1. Wikipedia - https://en.wikipedia.org/wiki/Binary_search_algorithm

2. geeksforgeeks - https://www.geeksforgeeks.org/binary-search/

3. geeksforgeeks - https://www.geeksforgeeks.org/exponential-search/

3. geeksforgeeks - https://www.geeksforgeeks.org/interpolation-search/

3. 종만북

2 Comments
댓글쓰기 폼