一些面試題裡,會出現 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
  1. int Bsearch(int *A, int n, int key)
  2. {
  3.     int low = 0, up = n-1, mid;
  4.     while(low<=up){
  5.         mid = (low+up)/2;
  6.         if(A[mid]==key) return mid;
  7.         else if(A[mid]>key) up=mid-1;
  8.         else low = mid+1;
  9.     }
  10.     return -1;
  11. }

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

 

2. recursive

 

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

Code Snippet
  1. int Bsearch(int *A, int low, int up, int key)
  2. {
  3.     if(low <= up) {
  4.         int mid = low + (up-low)/2;
  5.         if(key==A[mid])
  6.             return mid;
  7.         else if(key>A[mid])
  8.             return Bsearch(A, low, mid-1, key);
  9.         else
  10.             return Bsearch(A, mid+1, up, key);
  11.     }
  12.     return -1;
  13. }

 

3. Pointer 示之

 

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

Code Snippet
  1. int* Bsearch(int *A, int n, int key)
  2. {
  3.     int *pLow=A, *pUp=A+(n-1), *pMid;
  4.     while(pLow<=pUp){
  5.         pMid = pLow + (pUp - pLow) / 2;
  6.         if(*pMid == key) return pMid;
  7.         else if(*pMid > key) pUp = pMid-1;
  8.         else pLow = pMid+1;
  9.     }
  10.     return NULL;
  11. }

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

 

4. Variant : 無限元素搜尋

 

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

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

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

Code Snippet
  1. int BInfSearch(int *arr, int key)
  2. {
  3.     if(arr[0]==key) return 0;
  4.     else {
  5.         int low = 1, up = 2, mid;
  6.         while(arr[up]<key) low = up, up*=2;
  7.  
  8.         if(arr[up]==key) return up;
  9.         while(low<=up){
  10.             mid = (low + up)/2;
  11.             if(arr[mid]==key) return mid;
  12.             else if(arr[mid]>key) up = mid-1;
  13.             else low = mid+1;
  14.         }
  15.         return -1;
  16.     }
  17. }

 

5.  高效能

 

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

Code Snippet
  1. int Bsearch(int *A, int n, int key)
  2. {
  3.     int low=0, mid, lim;
  4.     for(lim = n; lim; lim>>=1){
  5.         mid = low + (lim>>1);
  6.         if(A[mid]==key) return mid;
  7.         else if(A[mid]<key) {
  8.             low = mid+1;
  9.             --lim;
  10.         }
  11.     }
  12.     return -1;
  13. }

 

6.  bsearch 實作


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

Code Snippet
 
  1. void * Bsearch (
  2.     const void * key,
  3.     const void * base,
  4.     size_t arr_num,
  5.     size_t ele_size,
  6.     int ( * comparator ) ( const void *, const void * ) )
  7. {
  8.     char *low = (char*)base;
  9.     char *up  = (char*)base + (arr_num-1)*ele_size;
  10.     char *mid;
  11.     size_t half;
  12.     int rst;
  13.     while(low <= up){
  14.         half = arr_num >> 1;
  15.         if(half!=0){
  16.             mid = low + (arr_num&1 ? half : half-1) * ele_size;
  17.             rst = comparator((const void*)mid, key);
  18.             if(rst==0){
  19.                 return mid;
  20.             } else if(rst>0){
  21.                 up = mid - ele_size;
  22.                 arr_num = half - !(arr_num&1);
  23.             }else{
  24.                 low = mid + ele_size;
  25.                 arr_num = half;
  26.             }
  27.         }else if(arr_num!=0){
  28.             return comparator(key, low) ? NULL : low;
  29.         }else{
  30.             break;
  31.         }
  32.     }
  33.     return NULL;
  34. }

 

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

Code Snippet
  1. void * Bsearch (
  2.     const void * key,
  3.     const void * base_,
  4.     size_t arr_num,
  5.     size_t ele_size,
  6.     int ( * comparator ) ( const void *, const void * ) )
  7. {
  8.     char *base = (char*)base_;
  9.     int lim, cmp;
  10.     void *mid;
  11.  
  12.     for(lim = arr_num; lim!=0 ; lim>>=1){
  13.         mid = base + (lim>>1)*ele_size;
  14.         cmp = comparator(key, mid);
  15.         if(!cmp) {
  16.             return mid;
  17.         } else if(cmp>0) {
  18.             base = (char*)mid + ele_size;
  19.             --lim;
  20.         }
  21.     }
  22.     return NULL;
  23. }

 

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
  1. int Bsearch(int *A, int n, int key)
  2. {
  3.     int low = 0, up = n-1, mid;
  4.     while(low<up-1){
  5.         mid = (low+up)/2;
  6.         if(A[mid]>=key) {// 等於 k 時繼續找
  7.             up = mid;
  8.         } else {
  9.             low = mid;
  10.         }
  11.     }
  12.     if(A[low]==key) return low;
  13.     else if(A[up]==key) return key;
  14.     else return -1;
  15. }

 

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

Code Snippet
  1. int Bsearch(int *A, int n, int key)
  2. {
  3.     int low = 0, up = n-1, mid;
  4.     while(low<up-1){
  5.         mid = (low+up)/2;
  6.         if(A[mid]<=key) {// 等於 k 時繼續找
  7.             low = mid;
  8.         } else {
  9.             up = mid;
  10.         }
  11.     }
  12.     if(A[up]==key) return up;
  13.     else if(A[low]==key) return low;
  14.     else return -1;
  15. }

 

 (3) 求最大 Idx 使得 A[Idx] < key 成立

這問題答案,先求最小 Idx 使得 A[Idx]==key 成立,答案再減1。

 

(4) 求最小 Idx 使得 A[Idx] > key 成立

相似,等於是先求最大 Idx 使得 A[Idx]==key 成立,答案再加1。

 

上面 (1)、(2) 之程式碼都未最佳化過,可以先將等於排除在外(如此一來 up / low 的更新就會+-1,邊界條件 -2 ),尋找到後再跳出,依上述規則搜尋最大 Idx / 最小 Idx,就不再示範。

 

9. 其他

 

本文並未收錄全部之 binary search 議題,像是均值定理的變型等,這些不再進行贅述。

edisonx 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • 康維哲
  • recursive那裏的判斷是否有錯~感覺怪怪
  • 是嗎?可舉個反例?

    edisonx 於 2016/10/08 03:07 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼

【 X 關閉 】

【PIXNET 痞客邦】國外旅遊調查
您是我們挑選到的讀者!

填完問卷將有機會獲得心動好禮哦(注意:關閉此視窗將不再出現)

立即填寫取消