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

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

3、二分查找算法   int BinSearch(SeqList R，KeyTypeK)      {//在有序表R[1..n]中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回零       int low=1，high=n，mid；//置當(dāng)前查找區(qū)間上、下界的初值       while(low<=high){ //當(dāng)前查找區(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]中查找        }//重點(diǎn)注意   ：輸出的時(shí)候?yàn)?quot;left-1",因?yàn)椋魹閙id，則可能沒有驗(yàn)證最后一次，若為left或者right同理沒有驗(yàn)證，right-1是不符合要求的，mid-1更不可以，因?yàn)閙id并不確定它的變化大小。        return 0；//當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗      } //BinSearh