二元搜尋次數

作者eduzone (eduzone)

看板Grad-ProbAsk

標題二元搜尋次數

時間Sun Aug 12 22:42:03 2018

一陣列內有62筆資料以二元搜尋最多需比較幾次? 時間複雜度為O(log2N) 最差次數1+(log2N) 擬答1+(log2*62)=19 (error!) 還請問正確計算方式 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.105.157 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1534084925.A.CAB.html

推 miachen8604: ceiling(lg62) = 6 08/12 23:10

推 y2j60537: 應該是ceiling(log(62+1))吧 08/12 23:37

推 miachen8604: 樓上正確，我忘了要+1 08/12 23:45

→ eduzone: log2N=62, ceiling N=6不知正確? 08/12 23:54

推 wilson50101: 想問一下如果bst是斜的是不是就是62次了 08/12 23:59

推 EXPCDR: 樓上他是問二元搜尋不是問二元搜尋樹 08/13 00:10

推 EXPCDR: 二元搜尋樹最糟搜尋來到O(n)每錯 08/13 00:13