實驗二 折半查找算法設計題目：折半查找算法設計問題描述：（1）分析掌握折半查找算法思想，在此基礎上，設計出遞歸算法和循環結構兩種實現方法的折半查找函數。（2）編寫程序實現：在保存于數組的10000個有序數據元素中查找數據元素x是否存在。數據元素x要包含兩種情況：一種是數據元素x包含在數組中；另一種是數據元素x不包含在數組中（3）數組中數據元素的有序化既可以初始賦值時實現，也可以設計一個排序函數實現。（4）根據兩種方法的實際運行時間，進行兩種方法時間效率的分析對比。基本要求：（1）10000個數據可以初始賦值時實現，也可以調用系統的隨機函數，再設計一個排序函數實現。（2）兩種方法時間效率的分析對比可以有兩種方法，一種是理論分析方法，一種是實際記錄運行時間。（3）提交實驗報告。測試數據：運行算法時，當輸入的數據小于10000，例如輸入9999時，顯示該數據在數組中，下標為9998，并且分別顯示遞歸和循環結構下的時間；當輸入的數據大于10000時，例如輸入20000時，顯示這個這個數據不再該數組中。算法思想：設有數組a中元素按從小到大的次序排列，a的下界下標為low， 上界下標為high，首先計算出a的中間位置下標mid=（low+high)/2,1.遞歸算法思想：比較x和amid,若x=amid，則查找成功；若xamid，則隨后調用算法自身在下標為mid+1，上界下標為high的區間繼續查找。當查找區間小于等于0時，查找過程結束。2.循環結構思想：用while(low = high)控制循環，比較x和amid，若x=amid，則查找成功；若xamid，則隨后在下標為mid+1，上界下標為high的區間繼續查找。當查找區間小于等于0時，查找過程結束。模塊劃分：1.頭文件time.h中包含time()和difftime(end,start)函數，分別實現取系統當前時間和end減去start的時間差； 2.頭文件stdlib.h中包含rand()函數，實現隨機數的生成；3.void list(int a)實現對隨機數從小到大的排序；4.int Search(int a,int low,int high,int x)用遞歸算法實現折半查找數據元素的函數；5.int BSearch(int a, int low, int high, int x)用循環結構實現折半查找數據元素的函數；6.void main()主函數，測試用遞歸算法和循環結構實現折半查找數據元素的函數。數據結構：源程序：#include#includeint Bsearch(int a,int x,int low,int high)int mid;if(lowhigh) return -1;mid=(low+high)/2;if(x=amid) return mid;else if(xamid)Bsearch(a,x,low,mid-1);elsereturn Bsearch(a,x,mid+1,high);int Csearch(int test,int x,int low,int high)for(int i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;void main()time_t start,end;double dif;int Bsearch(int a,int x,int low,int high);int Csearch(int test,int x,int low,int high);int a10000,x;int low=0,high=10000,mid=0;printf(請輸入要查找的元素：n);scanf(%ld,&x);printf(x=%ldn,x);for(int i=0;ihigh;i+)ai=i+1;int bn; time(&start);bn=Bsearch(a,x,0,10000);if(bn=-1) printf(x不在數組a中 ！n);else printf(x在數組a中，下標為%dn,bn);time(&end);dif=difftime(end,start);printf(遞歸折半方法耗時為：%f秒n,dif); int flag; time(&start);flag=Csearch(a,x,0,10000);if(flag=-1) printf(x不在數組a中！n);else printf(x在數組a中，下標為%ldn,flag);time(&end); dif=difftime(end,start);printf(循環折半算法耗時為：%f秒n,dif); 測試