查找 - 線性表的查找 - 二分查找（一）

　　二分查找

　　二分查找(Binary Search)

　　二分查找又稱折半查找它是一種效率較高的查找方法

　　二分查找要求線性表是有序表即表中結點按關鍵字有序並且要用向量作為表的存儲結構不妨設有序表是遞增有序的

　　二分查找的基本思想

　　二分查找的基本思想是(設R[lowhigh]是當前的查找區間)

　　()首先確定該區間的中點位置

　　

　　()然後將待查的K值與R[mid]key比較若相等則查找成功並返回此位置否則須確定新的查找區間繼續二分查找具體方

　　法如下

　　①若R[mid]key>K則由表的有序性可知R[midn]keys均大於K因此若表中存在關鍵字等於K的結點則該結點必定是在位

　　置mid左邊的子表R[mid]中故新的查找區間是左子表R[mid]

　　②類似地若R[mid]key

　　找是針對新的查找區間進行的。

　　因此，從初始的查找區間R[1..n]開始，每經過一次與當前查找區間的中點位置上的結點關鍵字的比較，就可確定查找是否成功

　　，不成功則當前的查找區間就縮小一半。這一過程重復直至找到關鍵字為K的結點，或者直至當前的查找區間為空(即查找失敗)時為

　　止。

　　3、二分查找算法

　　int BinSearch(SeqList R，KeyType K)

　　{ //在有序表R[1..n]中進行二分查找，成功時返回結點的位置，失敗時返回零

　　int low=1，high=n，mid; //置當前查找區間上、下界的初值

　　while(low<=high){ //當前查找區間R[low..high]非空

　　mid=(low+high)/2;

　　if(R[mid].key==K) return mid; //查找成功返回

　　if(R[mid].kdy>K)

　　high=mid-1; //繼續在R[low..mid-1]中查找

　　else

　　low=mid+1; //繼續在R[mid+1..high]中查找

　　}

　　return 0; //當low>high時表示查找區間為空，查找失敗

　　} //BinSeareh

　　二分查找算法亦很容易給出其遞歸程序【參見練習】

　　4、 二分查找算法的執行過程

　　設算法的輸入實例中有序的關鍵字序列為

　　(05，13，19，21，37，56，64，75，80，88，92)

From:http://tw.wingwit.com/Article/program/sjjg/201311/23861.html