作者bnm51315 (辛苦的耕耘)
看板TransCSI
標題Re: [問題] 二元搜尋法問題?
時間Mon Apr 13 04:42:27 2009
※ 引述《kenny607013 (Kenny)》之銘言：
: 使用二元搜尋法(binary search),在2000筆資料中,搜尋某一特定資料,最多會比對幾次?(A)100(B)11(C)50(D)1000
: 解答是給(B)11
: 我不確定要怎麼算
: 用二元演算法算嗎?
: /
它的算法是
以2為底取對數所得的值
以本題來說
就是log 2000
2
算出來的值是10.~
所以取成11 ( 因為是最多比對幾次 )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.22.18.79
1F：推 RJking:原理是每次取中間的資料比對，沒找到的話比中間小就找左半 04/13 22:38
2F：→ RJking:部，比中間大就找右半部(假設資料由小到大排序過)直到中間 04/13 22:39
3F：→ RJking:的值為要搜尋的值為止...好像原PO應該已經知道了 04/13 22:40
4F：→ RJking:所以數值小的話畫BST求樹高，數值大的話用bnm51315大的作法 04/13 22:43