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

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

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

可以對(duì)n個(gè)元素的有序數(shù)組進(jìn)行二叉搜索，通過(guò)繪制二叉決策樹(shù)來(lái)分析要分析的比較數(shù)。二叉決策樹(shù)的高度為[log2（n）]1級(jí)，這是二叉搜索的最大比較次數(shù)。例如，如果n=1000，則最大比較次數(shù)為[log2（1000）]1=9，1=10。如果要計(jì)算平均比較次數(shù)，則需要分析二叉決策樹(shù)中的每個(gè)節(jié)點(diǎn)。第一級(jí)比較一次，第二級(jí)比較兩次，第三級(jí)比較三次，以此類(lèi)推，將每個(gè)節(jié)點(diǎn)的比較次數(shù)相加，然后節(jié)點(diǎn)數(shù)（元素?cái)?shù)）就是平均比較次數(shù)。這里，假設(shè)搜索是在等概率條件下進(jìn)行的。例如：有一個(gè)由九個(gè)元素組成的有序數(shù)組，每個(gè)元素用1，2，3。。。8, 9. 然后二叉決策樹(shù)如下：如圖所示，如果要查找的元素位于第五個(gè)位置，則只需進(jìn)行一次比較即可找到它。如果找到第九個(gè)元素，就需要四個(gè)比較。該算法分別比較第五、第七、第八和第九個(gè)元素。因此，平均比較次數(shù)如下：你能理解這個(gè)分析嗎？希望能對(duì)你有所幫助。

C語(yǔ)言，二分法查找次數(shù)公式怎么推導(dǎo)？

順序搜索的基本思想是遍歷整個(gè)列表，并將記錄的關(guān)鍵字與給定值逐一進(jìn)行比較。如果記錄的關(guān)鍵字等于給定值，則搜索成功并找到記錄。如果關(guān)鍵字與最后一條記錄的給定值之間的比較不相等，則表中沒(méi)有記錄，搜索失敗。

二進(jìn)制搜索的基本思想是：

在有序表中，以中間記錄作為比較對(duì)象。如果給定值等于中間記錄的關(guān)鍵字，則搜索成功；如果給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半部分繼續(xù)搜索；如果給定值大于中間記錄的關(guān)鍵字，則在右半部分繼續(xù)搜索中間記錄的一半。重復(fù)上述過(guò)程，直到找到為止。