二、二分法查找（折半查找）的基本思想：
前提：
（1）確定該區(qū)間的中點(diǎn)位置：mid=（low+high）/2
min代表區(qū)間中間的結(jié)點(diǎn)的位置，low代表區(qū)間最左結(jié)點(diǎn)位置，high代表區(qū)間最右結(jié)點(diǎn)位置
（2）將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則確定新的查找區(qū)間：
如果R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在R[mid].key左邊的表中。這時(shí)high=mid-1
如果R[mid].key<a,則等于a的關(guān)鍵字如果存在，必然在R[mid].key右邊的表中。這時(shí)low=mid
如果R[mid].key=a，則查找成功。
（3）下一次查找針對(duì)新的查找區(qū)間，重復(fù)步驟（1）和（2）
（4）在查找過程中，low逐步增加，high逐步減少，如果high<low，則查找失敗。
平均查找長(zhǎng)度=Log2(n+1)-1
注：雖然二分法查找的效率高，但是要將表按關(guān)鍵字排序。而排序本身是一種很費(fèi)時(shí)的運(yùn)算，所以二分法比較適用于順序存儲(chǔ)結(jié)構(gòu)。為保持表的有序性，在順序結(jié)構(gòu)中插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。因此，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)而又經(jīng)常需要查找的線性表。
喜歡 
頂
難過
囧
圍觀
無聊
