二分法查找的平均查找長(zhǎng)度！~？在做這類問題時(shí)，我們應(yīng)該畫一棵二叉樹。然后把葉子補(bǔ)好。葉的高度是失敗的搜索數(shù)。然后，總和除以葉數(shù)就是失敗查找的平均長(zhǎng)度。非葉節(jié)點(diǎn)是成功的，高度是搜索成功的次數(shù)，再除以非葉

二分法查找的平均查找長(zhǎng)度！~？

在做這類問題時(shí)，我們應(yīng)該畫一棵二叉樹。然后把葉子補(bǔ)好。葉的高度是失敗的搜索數(shù)。然后，總和除以葉數(shù)就是失敗查找的平均長(zhǎng)度。非葉節(jié)點(diǎn)是成功的，高度是搜索成功的次數(shù)，再除以非葉節(jié)點(diǎn)的數(shù)量是成功的平均長(zhǎng)度。對(duì)于11個(gè)節(jié)點(diǎn)，二叉樹的成功搜索長(zhǎng)度為（1x1 2x2 3x4 4x4）/11=33/11，失敗的搜索長(zhǎng)度為（4x8 3x4）/（84）=44/12

二層正解

最壞的情況是深度為n的單叉樹為（N1）/2

最好的情況是形狀均勻，半搜索約為log2n

PS:如果構(gòu)造完成，例如：

則平均搜索長(zhǎng)度為：（1×12×23×4×3）/10=2.9