問題描述：
給定已排好序的n個元素組成的陣列，現要利用二分搜索演算法判斷特定元素x是否在該有序陣列中，
細節須知：
（1）由于可能需要對分治策略實作二分搜索的演算法效率進行評估，故使用大量的亂數對演算法進行實驗（生成亂數的方法見前篇隨筆），
（2）由于二分搜索需要資料為有序的，故在進行搜索前利用函式庫中sort函式對輸入的資料進行排序，
（3）代碼主要用到的是經典的二分查找加上遞回，
（4）其中limit為所要從亂數檔案中提取的資料的數量，以此為限來決定演算法需要在多少個資料中進行搜索，
（5）為了使代碼更人性化，加入了查找成功與失敗的提醒，主要區別于Search函式中的回傳值，若查找成功則回傳1（滿足1>0，即為查找成功）,其余則回傳0，即為查找失敗，
（6）通過clock函式對演算法運行的時間進行計算以評估演算法效率，
演算法原理：
假設搜索范圍為陣列a中的n個元素，要搜索的元素為x，
將n個元素分成個數大致相同的兩半，取a[n/2]與x進行比較，如果x=a[n/2]，則找到x，演算法終止，如果x<a[n/2]，則只要在陣列a的左半部繼續搜索x，如果x>a[n/2]，則只要在陣列a的右半部繼續搜索x，以此不斷地將搜索范圍折半，從而實作采用分治策略進行二分搜索，
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) //查找成功回傳116 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 else23 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 else59 cout<<"Can not find it!"<<endl;60 61 last = clock();62 63 cout<<"Time cost: "<<last-first<<endl;64 65 return 0;66 }
程式設計思路：
若x等于中間項，則退出，否則，
（1）將陣列劃分為兩個子陣列，其大小大約為原陣列的一半，如果x小于中間項，則選擇左子陣列；如果x大于中間項，則選擇右子陣列，
（2）確定x是否在該子陣列中，以解決該子陣列，如果該子陣列不夠小，則進行遞回處理，
（3）由子陣列的答案獲得原陣列的答案，
結果資料格式為time_t格式相減得到的長整型，
時間復雜性分析：
假設搜索范圍為陣列a中的n個元素，要搜索的元素為x，
將n個元素分成個數大致相同的兩半，取a[n/2]與x進行比較，如果x=a[n/2]，則找到x，演算法終止，如果x<a[n/2]，則只要在陣列a的左半部繼續搜索x，如果x>a[n/2]，則只要在陣列a的右半部繼續搜索x，以此不斷地將搜索范圍折半，從而實作采用分治策略進行二分搜索，
其中，每執行一次演算法的回圈，待搜索陣列的大小減少一半，在最壞情況下（即x大于所有陣列項），如果n是2的冪，而且x大于所有陣列專案，那每次呼叫生成的實體恰好為原實體的一半；若n=1，且x大于這個唯一陣列專案，會將x與此專案進行比較，后面是在low>high條件下的一次遞回呼叫，因而，確定遞推關系：
W（n）=W（n/2）+1 （n>1,n為2的冪）
W（1）=1
由Master方法可以得到
W（n）=lgn+1
如果n不僅局限于2的冪，則
W（n）=⌊lgn⌋+1∈O（lgn）
其中⌊y⌋表示小于或等于y的最大整數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/1874.html
標籤：Dart
上一篇：FlutterGo 后端知識點提煉:midway+Typescript+mysql(sequelize)
下一篇：Dart資料型別