數(shù)據(jù)結(jié)構(gòu)-基于C++語(yǔ)言（微課版） 課件 1-1 折半查找

折半查找的算法思想；折半查找的實(shí)現(xiàn)；折半查找的性能分析。本節(jié)目錄：本節(jié)內(nèi)容：折半查找有序表的折半查找

有序表的折半查找

使用條件：線性表中的記錄必須按關(guān)鍵碼有序；必須采用順序存儲(chǔ)?；舅枷耄涸谟行虮碇?，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)記錄，查找失敗。有序表的折半查找

折半查找的基本思想：

[r1………rmid-1]rmid[rmid+1………rn]如果k<rmid如果k>rmid查找左半?yún)^(qū)查找右半?yún)^(qū)k（mid=(1+n)/2）有序表的折半查找

例：查找值為14的記錄的過(guò)程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14非遞歸算法intBinSearch(intr[],intn,intk)//數(shù)組r[1]~r[n]存放查找集合{low=1;high=n;while(low<=high){mid=(low+high)/2;if(k<r[mid]) high=mid-1;elseif(k>r[mid]) low=mid+1;else returnmid;}return0;}有序表的折半查找

有序表的折半查找

遞歸算法intBinSearch(intr[],intlow,inthigh,intk){if(low>high) return0;else{mid=(low+high)/2;if(k<r[mid])returnBinSearch(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch(r,mid+1,high,k);else returnmid;}}有序表的折半查找

折半查找的查找性能可以使用二叉查找樹(shù)來(lái)分析。樹(shù)中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的記錄的位置。二叉查找樹(shù)的構(gòu)造方法：

⑴當(dāng)n=0時(shí)，二叉查找樹(shù)為空；

⑵當(dāng)n＞0時(shí)，二叉查找樹(shù)的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹(shù)是與有序表r[1]~r[mid-1]相對(duì)應(yīng)的二叉查找樹(shù)，根結(jié)點(diǎn)的右子樹(shù)是與r[mid+1]~r[n]相對(duì)應(yīng)的二叉查找樹(shù)。有序表的折半查找

11個(gè)結(jié)點(diǎn)的二叉查找樹(shù)的構(gòu)造－11－22－33－44－510－1111－9－108－97－85－66－7內(nèi)部結(jié)點(diǎn)外部結(jié)點(diǎn)3691011784512有序表的折半查找

具有n個(gè)結(jié)點(diǎn)的二叉查找樹(shù)的深度為h＝查找成功：在表中查找任一記錄的過(guò)程，即是二叉查找樹(shù)中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹(shù)中的層數(shù)。查找失?。翰檎沂〉倪^(guò)程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。從折半查找判定樹(shù)上容易看出，無(wú)論是查找成功還是查找失敗，關(guān)鍵碼的比較次數(shù)都小于等于二叉查找