《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件7-02二分查找

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧 二分查找常州信息職業(yè)技術(shù)學(xué)院0203線性表查找二分查找1、基本思想：設(shè)Rlow.high是當(dāng)前的查找區(qū)間。（1）首先確定該區(qū)間的中點(diǎn)位置：mid=(low+high)/2;（2）然后將待查找的K值與Rmid.key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：若Rmid.keyK，則由表的有序性可知Rmidn. key均大于K，因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn),則該結(jié)點(diǎn)必定是在位置mid左邊的子表R1mid-1中，故新的查找區(qū)間是左子表R1.mid-1；若Rmid.keyK，類似地，則新的查找區(qū)

2、間是右子表Rmid+1n。下次在新的查找區(qū)間進(jìn)行查找。二分查找（binary search）：二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，不妨設(shè)有序表是遞增有序的。并且要用順序存儲(chǔ)結(jié)構(gòu)作為表的存儲(chǔ)結(jié)構(gòu)。04二分查找 說(shuō)明從初始的查找區(qū)間R1.n開(kāi)始，每經(jīng)過(guò)一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上結(jié)點(diǎn)關(guān)鍵字的比較，若相等則查找成功，否則當(dāng)前查找區(qū)間就縮小一半。重復(fù)這一過(guò)程直至找到關(guān)鍵字為K的結(jié)點(diǎn)，或者當(dāng)前查找區(qū)間為空，即查找失敗為止。int BinSearch(SeqList R,KeyType K) /在有序表R1.n中進(jìn)行二分查找，成功時(shí)返回

3、結(jié)點(diǎn)位置，失敗時(shí)返回零int low=1,high=n,mid;/置當(dāng)前查找區(qū)間的初值while(lowK)high=mid-1; /繼續(xù)在Rlow.mid-1中查找elselow=mid+1;/繼續(xù)在Rmid+1.high中查找return 0;/當(dāng)lowhigh時(shí)查找區(qū)間為空，查找失敗 2、具體算法053、二分查找法實(shí)例二分查找 已知有序順序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找過(guò)程中，方括號(hào)表示當(dāng)前待查找記錄的區(qū)間，分別對(duì)應(yīng)下標(biāo)low和high；下劃線表示當(dāng)前查找記錄的關(guān)鍵字，對(duì)應(yīng)下標(biāo)mid。下標(biāo)1234567

4、891011K第1次比較051319213756647580889221第2次比較0513192137566475808892第3次比較0513192137566475808892查找K=21的過(guò)程如下：查找K=21成功，返回下標(biāo)mid=4。LH063、二分查找法實(shí)例二分查找 已知有序順序表R（05,13,19,21,37,56,64,75,80,88,92），采用二分查找法查找K=21和K=78。查找過(guò)程中，方括號(hào)表示當(dāng)前待查找記錄的區(qū)間，分別對(duì)應(yīng)下標(biāo)low和high；下劃線表示當(dāng)前查找記錄的關(guān)鍵字，對(duì)應(yīng)下標(biāo)mid。查找K=78的過(guò)程如下：查找K=78不成功，返回0。LH下標(biāo)1234567891011K第1次比較051319213756647580889278第2次比較0513192137566475808892第3次比較0513192137566475808892區(qū)間已空051319213756647580889207二分查找4、算法分析二分查找效率高，但要將表按關(guān)鍵字排序且只適用于順序存儲(chǔ)結(jié)構(gòu)，而不能用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)經(jīng)常進(jìn)行插入和刪除操作的表，不