[面試] binary search－Edison.X. Blog

一些面試題裡，會出現 binary search 演算法相關問題，此文以 binary search 之一些議題做為討論。

下述一些問題，實際上是可能合併出題的，唯避免此文過於流水，只做幾種題型之分析。討論時均假設陣列 A 已遞增排序過

0. 概念

A. Low = 0 , up = n-1
B. Mid = (up + low) / 2
C. 若 A[Mid] > Key , 太大, 更新上界 : up = Mid-1
D. 若 A[Mid] < Key , 太小, 更新下界 : low = Mid+1
E. 若 A[Mid] = Key, 剛好, 傳回 Mid
F. low<=up 成立, 回到步驟 B ; 否則傳回 can not find value.

1. 基本型

常見的 code 大概如下

Code Snippet
int Bsearch(int *A, int n, int key)
{
    int low = 0, up = n-1, mid;
    while(low<=up){
        mid = (low+up)/2;
        if(A[mid]==key) return mid;
        else if(A[mid]>key) up=mid-1;
        else low = mid+1;
    }
    return -1;
}

有個地方小挑，(low+up) / 2 之處，(low+up) 可能造成 overflow，故 mid 可修正為 low + (up-low)/2，位移取代除法就不贅述。

2. recursive

筆者不是建議用 recursive，只是一些面試真的會要求用 recursive 完成這問題。

Code Snippet
int Bsearch(int *A, int low, int up, int key)
{
    if(low <= up) {
        int mid = low + (up-low)/2;
        if(key==A[mid])
            return mid;
        else if(key>A[mid])
            return Bsearch(A, low, mid-1, key);
        else
            return Bsearch(A, mid+1, up, key);
    }
    return -1;
}

3. Pointer 示之

上述是傳回陣列 index，為一整數，找不到時傳回-1；另一種模式是傳回 int* ，找不到時傳回 NULL。

Code Snippet
int* Bsearch(int *A, int n, int key)
{
    int *pLow=A, *pUp=A+(n-1), *pMid;
    while(pLow<=pUp){
        pMid = pLow + (pUp - pLow) / 2;
        if(*pMid == key) return pMid;
        else if(*pMid > key) pUp = pMid-1;
        else pLow = pMid+1;
    }
    return NULL;
}

說明上為簡潔，此文盡可能以 index 操作為示例。

4. Variant : 無限元素搜尋

binary search 一種變型。假設欲搜尋 key, 一開始必須先確定上、下限，作法如下。

Code Snippet
int low = 1, up = 2;
while(arr[up]<key)
    low = up, up*=2;

上面可確保 arr[low] < key <= arr[up]，再對 arr[low:up] 做普通的二分搜尋法即可。

Code Snippet
int BInfSearch(int *arr, int key)
{
    if(arr[0]==key) return 0;
    else {
        int low = 1, up = 2, mid;
        while(arr[up]<key) low = up, up*=2;
 
        if(arr[up]==key) return up;
        while(low<=up){
            mid = (low + up)/2;
            if(arr[mid]==key) return mid;
            else if(arr[mid]>key) up = mid-1;
            else low = mid+1;
        }
        return -1;
    }
}

5. 高效能

這版程式碼不好讀，算出之結果和上述的結果有誤差存在 (但可以確定找到的一定是 key, 只是 key 如果重覆的話找到的位置未必會一樣)。

Code Snippet
int Bsearch(int *A, int n, int key)
{
    int low=0, mid, lim;
    for(lim = n; lim; lim>>=1){
        mid = low + (lim>>1);
        if(A[mid]==key) return mid;
        else if(A[mid]<key) {
            low = mid+1;
            --lim;
        }
    }
    return -1;
}

6. bsearch 實作

http://www.jbox.dk/sanos/source/lib/bsearch.c.html

Code Snippet
 
void * Bsearch (
    const void * key,
    const void * base,
    size_t arr_num,
    size_t ele_size,
    int ( * comparator ) ( const void *, const void * ) )
{
    char *low = (char*)base;
    char *up  = (char*)base + (arr_num-1)*ele_size;
    char *mid;
    size_t half;
    int rst;
    while(low <= up){
        half = arr_num >> 1;
        if(half!=0){
            mid = low + (arr_num&1 ? half : half-1) * ele_size;
            rst = comparator((const void*)mid, key);
            if(rst==0){
                return mid;
            } else if(rst>0){
                up = mid - ele_size;
                arr_num = half - !(arr_num&1);
            }else{
                low = mid + ele_size;
                arr_num = half;
            }
        }else if(arr_num!=0){
            return comparator(key, low) ? NULL : low;
        }else{
            break;
        }
    }
    return NULL;
}

http://www.koders.com/c/fid541FB7CBA11966C205E4ED51F3B95E459BE1AA10.aspx

Code Snippet
void * Bsearch (
    const void * key,
    const void * base_,
    size_t arr_num,
    size_t ele_size,
    int ( * comparator ) ( const void *, const void * ) )
{
    char *base = (char*)base_;
    int lim, cmp;
    void *mid;
 
    for(lim = arr_num; lim!=0 ; lim>>=1){
        mid = base + (lim>>1)*ele_size;
        cmp = comparator(key, mid);
        if(!cmp) {
            return mid;
        } else if(cmp>0) {
            base = (char*)mid + ele_size;
            --lim;
        }
    }
    return NULL;
}

8. Variant : 找出特定位置(首、末) 出現之元素

上述任何一版之 binary search ，找到的元素值並不能保證是重覆元素的第一個，如

int Arr[10] = {1,2,2,2,2,2,2,2,2,3} ;

對 Arr 搜尋 2 時，得到的 position 會是 4 ，但在某些情況下，想拿到的結果是 position = 1 。

這類型的變化很繁雜，大致如下所述。

(1) 求最小 idx 使得 A[idx] == key 成立

Code Snippet
int Bsearch(int *A, int n, int key)
{
    int low = 0, up = n-1, mid;
    while(low<up-1){
        mid = (low+up)/2;
        if(A[mid]>=key) {// 等於 k 時繼續找
            up = mid;
        } else {
            low = mid;
        }
    }
    if(A[low]==key) return low;
    else if(A[up]==key) return key;
    else return -1;
}

(2) 求最大 idx 使得 A[idx] == key 成立

Code Snippet
int Bsearch(int *A, int n, int key)
{
    int low = 0, up = n-1, mid;
    while(low<up-1){
        mid = (low+up)/2;
        if(A[mid]<=key) {// 等於 k 時繼續找
            low = mid;
        } else {
            up = mid;
        }
    }
    if(A[up]==key) return up;
    else if(A[low]==key) return low;
    else return -1;
}