分享到plurk 分享到twitter 分享到facebook

acm/course/Binary_Search

Week 4: Binary Search

Binary Search(二元搜尋法)

說明: 一種在有序陣列中尋找某一特定元素的搜尋演算法,原理為將欲搜尋的值,與所有資料的中間值(中位數)做比對。

步驟

  1. 資料需依大小先排序好
  2. Middle = ⌊(Left + Right)/2⌋
  3. 將鍵值key與搜尋範圍的中間資料data[Middle]作比對
    • key = data[Middle]:找到
    • key < data[Middle]:縮小搜尋範圍 ⇒ Right = Middle-1
    • key > data[Middle]:縮小搜尋範圍 ⇒ Left = Middle+1
  4. 重複上步驟,直到找到資料或搜尋範圍交叉(找不到)

舉例

從排序好的陣列中,找出小於 34的最大值


Index of mid = (L+R+1)/2 = (0+14+1)/2 = 7


判斷mid有沒有小於34 => 沒有,找左半部


Index of mid = (L+R+1)/2 = (0+6+1)/2 = 3


判斷mid有沒有小於34 => 有,找右半部


Index of mid = (L+R+1)/2 = (4+6+1)/2 = 5


判斷mid有沒有小於34 => 沒有,找左半部


小於34的最大值 = 33


實作

#include <cstdio>

int binary_search(int *numbers, int n, int val) {
	int left = 0, right = n - 1;
	while(left < right) {
		int middle = (left + right) / 2;
		if (numbers[middle] < val) {
			left = middle + 1;
		} else {
			right = middle - 1;
		}
	}
	return right;
}

int main() {
	int array[] = {6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97};
 	printf("%d\n", binary_search(array, 15, 34));    // 10 50 60 

	return 0;
} 

時間複雜度

T(n) = T(n/2) + Ο(1) = Ο(lgn)