[ 資料結構 小學堂 ] 搜尋 : 二元搜尋法

前言 : 
如果要搜尋的資料已經事先排序好, 則可以使用 二元搜尋法 (Binary Search) 來進行搜尋. 二元搜尋法 是將資料分割成兩等份, 再比較鍵值與中間值的大小, 如果鍵值小於中間值, 可以確定要找的資料再前半段的元素, 否則在後半部. 如此分割數次直到找到或確定不存在為止. 

二元搜尋法範例說明 : 
考慮有已排序序數列 2, 3, 5, 8, 9, 11, 12, 16, 18 而要搜尋值為 11 時 : 
Step1 : 首先更第五個數值9 比較, 因為11 > 9, 所以往後半部移動. 

2, 3, 5, 8, 9, 11, 12, 16, 18 #11<9

Step2 : 接著選擇後半段中間值 12 比較, 因為11 < 12, 所以往前半部移動. 

2, 3, 5, 8, 9, 11, 12, 16, 18 # 11<12

Step3 : 因為前半部只剩下11=11, 表示搜尋完成. 

二元法分析 : 

1. 時間複雜度 : 因為每次的搜尋都會比上一次少一半的範圍, 最多只需要比較 log2n+1 或 log2(n+1), 時間複雜度為 O(logn).
2. 二分法必須事先經過排序, 且資料量必須能直接在記憶體中執行.
3. 此法適合於不需增刪的靜態資料.

範例代碼 (C): 

view plaincopy to clipboardprint?

1. #include <iostream>  
2.   
3. using namespace std;  
4. int binarySearch(int data[50], int val){  
5.     int low=0, high=49, mid=0;  
6.     cout << "搜尋處理中..." << endl;  
7.     while(low<=high && val!=-1) {  
8.         mid = (low+high)/2;  
9.         if(val
10.             high = mid-1;  
11.             cout << val << " 介於 data[" << low << "]=" << data[low] << " 與 data[" << mid << "]" << data[mid] << endl;  
12.         } else if(val>data[mid]) {  
13.             low = mid+1;  
14.             cout << val << " 介於 data[" << mid << "]=" << data[mid] << " 與 data[" << high << "]" << data[high] << endl;  
15.         } else{  
16.             return mid;  
17.         }  
18.     }  
19.     return -1;  
20. }  
21. void main() {  
22.     int data[50] = {0}, val=1;  
23.     for(int i=0; i<50; i++) {  
24.         data[i] = val;  
25.         val+=(rand()%5+1);  
26.     }  
27.     int key=0, num;  
28.     while(1) {  
29.         cout << "請輸入搜尋值(1-150), 輸入-1結速: ";  
30.         cin >> key;  
31.         if(key<0)  
32.             break;  
33.         num = binarySearch(data, key);  
34.         if(num>=0) {  
35.             cout << "在第 " << num << "個位置找到 ( data[" << num << "]=" << data[num] << "." << endl;   
36.         } else {  
37.             cout << "##### 沒有找到 " << key << "#####" << endl;  
38.         }  
39.     }  
40. }  

執行結果 : 

請輸入搜尋值(1-150), 輸入-1結束: 23 <輸入值進行搜尋>
搜尋處理中...
23 介於 data[0]=1 與 data[24]72
23 介於 data[0]=1 與 data[11]39
23 介於 data[5]=17 與 data[10]38
23 介於 data[6]=22 與 data[8]30
23 介於 data[6]=22 與 data[7]26
23 介於 data[7]=26 與 data[7]26
##### 沒有找到 23#####
請輸入搜尋值(1-150), 輸入-1結束: 17
搜尋處理中...
17 介於 data[0]=1 與 data[24]72
17 介於 data[0]=1 與 data[11]39
在第 5個位置找到 ( data[5]=17.)

範例代碼 (Python): 
Python 的內建 library bisect 可以提供類似 Binary Search 的功能: 
Source code link: 

view plaincopy to clipboardprint?

1. from bisect import bisect_left  
2.   
3. def binary_search(a, x):  
4.     i = bisect_left(a, x)  
5.     if i != len(a) and a[i] == x:  
6.         return i  
7.     else:  
8.         return -1  
9.   
10. # Driver code  
11. a  = [1, 2, 4, 4, 8]  
12.   
13. for v in [1, 4, 5, 0]:  
14.     i = binary_search(a, v)  
15.     if i == -1:  
16.         print("{} is not in list={}!".format(v, a))  
17.     else:  
18.         print("{} is at position {} in list={}".format(v, i, a))  

Execution result: 

1 is at position 0 in list=[1, 2, 4, 4, 8]
4 is at position 2 in list=[1, 2, 4, 4, 8]
5 is not in list=[1, 2, 4, 4, 8]!
0 is not in list=[1, 2, 4, 4, 8]!

補充說明 : 
* Wiki : Binary Search 

In computer science, a binary search is an algorithm for locating the position of an element in a sorted list. It inspects the middle element of the sorted list: if equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for further searching based on whether the sought value is greater than or less than the middle element...

* [C 範例代碼] 尋找演算法 : 二分查找 
* Use Case: HackerRank - Climbing the Leaderboard