1、二分查找(BinarySearch)   　二分查找又稱折半查找，它是一種效率較高的查找方法。   　二分查找要求：線性表是有序表，即表中結點按關鍵字有序，并且要用向量作為表的存儲結構。不妨設有序表是遞增有序的。

2、二分查找的基本思想   　二分查找的基本思想是：（設R[low,high]是當前的查找區(qū)間） （1）首先確定該區(qū)間的中點位置：                 （2）然后將待查的K值與R[mid].key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：  　①若R[mid].key>K，則由表的有序性可知R[mid,n].keys均大于K，因此若表中存在關鍵字等于K的結點，則該結點必定是在位置mid左邊的子表R[1,mid-1]中，故新的查找區(qū)間是左子表R[1,mid-1]。   　②類似地，若R[mid].key<K，則要查找的K必在mid的右子表R[mid+1,n]中，即新的查找區(qū)間是右子表R[mid+1,n]。下一次查找是針對新的查找區(qū)間進行的。   　因此，從初始的查找區(qū)間R[1,n]開始，每經(jīng)過一次與當前查找區(qū)間的中點位置上的結點關鍵字的比較，就可確定查找是否成功，不成功則當前的查找區(qū)間就縮小一半。這一過程重復直至找到關鍵字為K的結點，或者直至當前的查找區(qū)間為空(即查找失敗)時為止

3、二分查找算法   int BinSearch(SeqList R，KeyTypeK)      {//在有序表R[1..n]中進行二分查找，成功時返回結點的位置，失敗時返回零       int low=1，high=n，mid；//置當前查找區(qū)間上、下界的初值       while(low<=high){ //當前查找區(qū)間R[low,high]非空         mid=(low+high)/2；         if(R[mid].key==K) return mid；//查找成功返回         if(R[mid].kdy>K)            high=mid-1; //繼續(xù)在R[low,mid-1]中查找         else            low=mid+1；//繼續(xù)在R[mid+1,high]中查找        }//重點注意   ：輸出的時候為"left-1",因為，若為mid，則可能沒有驗證最后一次，若為left或者right同理沒有驗證，right-1是不符合要求的，mid-1更不可以，因為mid并不確定它的變化大小。        return 0；//當low>high時表示查找區(qū)間為空，查找失敗      } //BinSearh