折半查找時(shí)若數(shù)據(jù)元素個(gè)數(shù)為偶數(shù)怎么畫判定樹？構(gòu)建半搜索的決策樹就足夠了第一層有一個(gè)節(jié)點(diǎn)第二層有兩個(gè)節(jié)點(diǎn)第三層有四個(gè)節(jié)點(diǎn)第四層有八個(gè)節(jié)點(diǎn)，共124個(gè)節(jié)點(diǎn)[8=15剩下的30-15=15都在第五層，也就是

折半查找時(shí)若數(shù)據(jù)元素個(gè)數(shù)為偶數(shù)怎么畫判定樹？

構(gòu)建半搜索的決策樹就足夠了

第一層有一個(gè)節(jié)點(diǎn)

第二層有兩個(gè)節(jié)點(diǎn)

第三層有四個(gè)節(jié)點(diǎn)

第四層有八個(gè)節(jié)點(diǎn)，共124個(gè)節(jié)點(diǎn)[8=15

剩下的30-15=15都在第五層，也就是說比較的次數(shù)是5，所以答案是正確的

二進(jìn)制搜索一個(gè)有n個(gè)元素的有序數(shù)組。要分析的比較數(shù)可以通過繪制二叉決策樹來分析。二叉決策樹的高度為[log2（n）]1級(jí)，這是二叉搜索的最大比較次數(shù)。例如，如果n=1000，則最大比較次數(shù)為[log2（1000）]1=9，1=10。如果要計(jì)算平均比較次數(shù)，則需要分析二叉決策樹中的每個(gè)節(jié)點(diǎn)。第一級(jí)比較一次，第二級(jí)比較兩次，第三級(jí)比較三次，以此類推，將每個(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. 然后二叉決策樹如下：如圖所示，如果要查找的元素位于第五個(gè)位置，則只需進(jìn)行一次比較即可找到它。如果找到第九個(gè)元素，就需要四個(gè)比較。該算法分別比較第五、第七、第八和第九個(gè)元素。因此，平均比較次數(shù)如下：你能理解這個(gè)分析嗎？希望能對(duì)你有所幫助。

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

1. 例如，長度為10的二叉搜索決策樹的具體生成過程遵循左子節(jié)點(diǎn)<根節(jié)點(diǎn)<右子節(jié)點(diǎn)

2。對(duì)于長度為10的有序表中的二進(jìn)制搜索，無論搜索哪個(gè)記錄，都必須與中間記錄進(jìn)行比較，中間記錄為（1，10）/2=5（注意四舍五入，即向下舍入），即判定數(shù)的根為5。

3. 考慮決策樹的左子樹，即將搜索區(qū)域調(diào)整到左半部分，搜索間隔為[1,4]，則中值為（1,4）/2=2（注：舍入），所以子根節(jié)點(diǎn)為2

4?？紤]決策樹的右子樹，即將搜索區(qū)域調(diào)整到右半部分，搜索間隔為[6,10]，則中值為（6,10）/2=85。重復(fù)上述步驟，依次確定左右子項(xiàng)