2019年3月29日 星期五

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

前言 : 
如果要搜尋的資料已經事先排序好, 則可以使用 二元搜尋法 (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): 
  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
  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  = [12448]  
  12.   
  13. for v in [1450]:  
  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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...