1、實驗1/2搜索算法實驗報告一.實驗的目的1.理解分治算法的概念和基本要素；2.理解遞歸的概念；3.掌握設計有效算法的分治策略；4.通過二進制搜索技術學習分治策略設計技巧；二。實驗內(nèi)容和要求1.使用二進制搜索算法在任意N個有序序列中查找指定元素。2.通過計算機實驗實現(xiàn)算法。3.保存并打印程序運行結果，結合程序進行分析，并提交實驗報告。4.至少使用兩種方法進行編程。三。實驗原理二進制搜索算法也被稱為二進制搜索方法。它充分利用元素之間的順序關系，采用分治策略。在最壞的情況下，它可以使用0(log n)來完成搜索任務?；舅枷雽個元素分成兩部分，數(shù)量大致相同。取一個n/2，并將其與要搜索的X進行比較

2、。如果x=an/2，找到X，算法終止。如果xan/2，我們只需要繼續(xù)在數(shù)組a的右半部分搜索x。二分法的應用極其廣泛，其思想也很容易理解。第一個二進制搜索算法早在1946年就出現(xiàn)了，但是第一個完全正確的二進制搜索算法直到1962年才出現(xiàn)。本特利在他的書Writing Correct Programs中寫道，90%的計算機專家無法在2小時內(nèi)寫出完全正確的二進制搜索算法。問題的關鍵是準確定義每個搜索范圍的邊界和終止條件的確定，并正確地總結奇數(shù)和偶數(shù)的各種情況。事實上，經(jīng)過整理，可以發(fā)現(xiàn)它的具體算法非常直觀。方法1:直接搜索窮舉遍歷方法2:遞歸搜索#包括#定義最大30int BinarySearch(

3、int a，int x，int left，int right)if(leftright)返回-1；否則left=(左右)/2；if(x=a左)向左返回；其他if(xa左)二進制搜索(a，x，左1，右)；其他二進制搜索(a，x，左* 2-右，左1)；main()整數(shù)最大值；找到int，x，n，I，j，p；Printf(“輸入數(shù)量 n”)；scanf(“% d”，n)；Printf(“數(shù)組數(shù)據(jù) n”)；對于(I=0；iaj)p=j。if (p！=j)x=ap；ap=aI；aI=x；對于(I=0；i#定義最大30int BinarySearch(int a，int x，int n)int left=

4、0；int right=n-1；中間；而(左=右)middle=(左右)/2；如果(x=a中間)返回中間；if(xa中間)左=中間1；否則右=中間-1；返回-1；main()整數(shù)最大值；找到int，x，n，I，j，p；Printf(“數(shù)字數(shù) n”)；scanf(“% d”，n)；Printf(“數(shù)組數(shù)據(jù) n”)；對于(I=0；iaj)p=j。if (p！=j)x=ap；ap=aI；aI=x；對于(I=0；I陣列要查找的關鍵元素向左標志右-右標志(n-數(shù)據(jù)數(shù)量)Main()主函數(shù)：ound-是否找到標志，-1表示未找到，值找到下標要查找的x元素N-元素數(shù)量I，j，p回路控制變量(1)遞歸搜索#包

5、括#定義最大30int BinarySearch(int a，int鍵，int left，int right)int mid=(右-右)/2 left；如果(amid=鍵)返回中部；if(左=右)返回-1；否則如果(keyamid) 返回BinarySearch(a，鍵，中間1，右)；否則如果(keyaj)p=j。if (p！=j)x=ap；ap=aI；aI=x；Printf(排序數(shù)據(jù)如下：)；對于(I=0；i#定義最大30int BinarySearch(int a，int鍵，int len)int mid=len/2；if (key=amid) 返回中部；int left=0；int right=len-1；而(左=右) /迭代搜索mid=(右左)/2；if(keyamid) 左=中間1；其他返回中部；返回-1；int main(空)整數(shù)最大值；找到int，x，n，I，j，p；printf(數(shù)據(jù)個數(shù)：)；scanf(% d ，n)