二分查找
1、二分查找(Binary Search)
二分查找又稱折半查找，它是一種效率較高的查找方法。
二分查找要求：線性表是有序表，即表中結點按關鍵字有序，並且要用向量作為表的存儲結構。不妨設有序表是遞增有序的。
2、二分查找的基本思想
二分查找的基本思想是：（設R[low..high]是當前的查找區間）
（1）首先確定該區間的中點位置：
（2）然後將待查的K值與R[mid].key比較：若相等，則查找成功並返回此位置，否則須確定新的查找區間，繼續二分查找，具體方法如下：
①若R[mid].key>K，則由表的有序性可知R[mid..n].keys均大於K，因此若表中存在關鍵字等於K的結點，則該結點必定是在位置mid左邊的子表R[1..mid-1]中，故新的查找區間是左子表R[1..mid-1]。
②類似地，若R[mid].key<K，則要查找的K必在mid的右子表R[mid+1..n]中，即新的查找區間是右子表R[mid+1..n]。下一次查找是針對新的查找區間進行的。
因此，從初始的查找區間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
作者“志在千裡”
