由於可能需要對分治策略實現二分搜索的演算法效率進行評估，故使用大量的隨機數對演算法進行實驗（生成隨機數的方法見前篇隨筆）。 由於二分搜索需要數據為有序的，故在進行搜索前利用函數庫中sort函數對輸入的數據進行排序。 代碼主要用到的是經典的二分查找加上遞歸。 其中limit為所要從隨機數文件中提取的數據的 ...
由於可能需要對分治策略實現二分搜索的演算法效率進行評估，故使用大量的隨機數對演算法進行實驗（生成隨機數的方法見前篇隨筆）。
由於二分搜索需要數據為有序的，故在進行搜索前利用函數庫中sort函數對輸入的數據進行排序。
代碼主要用到的是經典的二分查找加上遞歸。
其中limit為所要從隨機數文件中提取的數據的數量，以此為限來決定演算法需要在多少個數據中進行搜索。
為了使代碼更人性化，加入了查找成功與失敗的提醒，主要區別於Search函數中的返回值，若查找成功則返回1（滿足1>0，即為查找成功）,其餘則返回0，即為查找失敗。
通過clock函數對演算法運行的時間進行計算以評估演算法效率。
1 #include <iostream>
2 #include <fstream> 3 #include <cstdlib> 4 #include <ctime> 5 #include <algorithm> 6 using namespace std; 7 #define limit 100000 8 9 int Search(int R[],int low,int high,int k) //low表示當前查找的範圍下界、high表示當前查找範圍的上界，k為所要查找的內容 10 { 11 int mid; 12 13 if (low<=high){ //查找區間存在一個及以上元素 14 mid=(low+high)/2; //求中間位置 15 if (R[mid]==k) //查找成功返回1 16 return 1; 17 if (R[mid]>k) //在R[low..mid-1]中遞歸查找 18 Search(R,low,mid-1,k); 19 else //在R[mid+1..high]中遞歸查找 20 Search(R,mid+1,high,k); 21 } 22 else 23 return 0; 24 } 25 26 int main(void) 27 { 28 ifstream fin; 29 int x; 30 int i; 31 int a[limit]; 32 int result; 33 34 fin.open("random_number.txt"); 35 if(!fin){ 36 cerr<<"Can not open file 'random_number.txt' "<<endl; 37 return -1; 38 } 39 40 time_t first, last; 41 42 for(i=0; i<limit; i++){ 43 fin>>a[i]; 44 } 45 fin.close(); 46 47 sort(a,a+limit); 48 49 cout<<"Please enter the number you want to find："; 50 cin>>x; 51 52 first = clock(); 53 54 result = Search(a,0,limit-1,x); 55 56 if(result>0) 57 cout<<"Search success!"<<endl; 58 else 59 cout<<"Can not find it!"<<endl; 60 61 last = clock(); 62 63 cout<<"Time cost: "<<last-first<<endl; 64 65 return 0; 66 }
