實驗報告7-查找算法

計算機科學(xué)與工程學(xué)院PAGEPAGE4《數(shù)據(jù)結(jié)構(gòu)》實驗報告

實驗內(nèi)容在VisualC++6.0環(huán)境下，利用C語言實現(xiàn)對順序有序序列進行二分查找。實驗詳細(xì)說明二分查找的基本思想如下：假設(shè)r[low..high]是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中間位置mid=(low+high)/2，然后將給定值k與有序表居中位置的關(guān)鍵字r[mid].key進行比較。比較結(jié)果又三種：若r[mid].key=k，則查找成功，返回該結(jié)點的位置mid；若r[mid].key＜k，則說明待查找的結(jié)點只可能在有序表的右子表中，接著只要在其右子表中繼續(xù)進行二分查找即可；若r[mid].key＞k，則說明待查找的結(jié)點只可能在有序表的左子表中，接著只要在其左子表中繼續(xù)進行二分查找即可。這樣每經(jīng)過一次比較，就縮小一半查找范圍，如此進行下去，直到找到關(guān)鍵字為k的結(jié)點或當(dāng)前查找區(qū)間為空（即查找失敗，條件是high＜low）時為止。主要代碼如下： while(begin<=end) { i=(begin+end)/2; if(x==a[i]) { printf("數(shù)據(jù)%d已找到，在第%d個位置\n",x,i+1); bfinded=true; break; } else if(x<a[i]) end=i-1; else begin=i+1; }試著自己編寫剩余代碼，對以下順序有序序列進行二分查找：inta[16]={2,4,5,7,8,11,23,26,30,36,39,40,41,45,58,67};#include<iostream>usingnamespacestd;voidSearch(inta[],intbegin,intend,intx){ intlow=begin; inthigh=end; while(low<=high) { intmid=(low+high)/2; if(x==a[mid]){ cout<<x<<"wasfound,in"<<mid<<endl;break;} elseif(x<a[mid]) high=mid-1; else low=mid+1; } if(low>high)cout<<x<<"isnotfound."<<endl;}intmain(){ inta[16]={2,4,5,7,8,11,23,26,30,36,39,40,41,45,58,67}; Search(a,0,15,30);}實驗中遇到的問題及解決方法、實驗結(jié)果（截圖）實驗