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

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

有序表的折半查找

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

折半查找的基本思想：

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

例：查找值為14的記錄的過程：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;}}有序表的折半查找

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

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

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

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

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