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

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

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

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

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

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

第四層有八個節(jié)點(diǎn)，總共1248=15

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

半搜索也是二進(jìn)制搜索，必須滿足排序關(guān)系。二叉搜索樹也可以用來搜索，一般復(fù)雜度是O（logn），最差的是O（n）。您還可以使用平衡樹進(jìn)行搜索，例如AVL、swap、splay等。您可以保留o（logn）。比二進(jìn)制搜索性能更好：可能只有散列。如果hash函數(shù)設(shè)計(jì)得好，可以認(rèn)為O（1）堆排序更有趣。這是值得研究的。理解之后，它是非常有用和重要的。