計算機概論-二分搜尋法

👨🏻‍🏫 學術台數學

[匿名]

2009-12-01 5:01 am

請問假設有一到九九個數字用二分搜尋在最雖的情況下要蒐幾次?

我怎麼看都是三次阿為何計概老師算四次?
我的做法:
1.2.3.4.5.6.7.8.9
第一次: 找到中間5 然後假設比他小
接著剩下 1.2.3.4 比較
然後取中間2 然後假設比他大
剩下3.4阿
第三次搜尋十答案不就出來了老師怎麼算四次 = =?

更新1:

神麼阿= = 剩下3.4十才第二次搜尋而已

回答 (3)

myisland8132

2009-12-01 8:15 pm

✔ 最佳答案

http://program-lover.blogspot.com/2008/08/binary-search.html
以 1,2,3,4,5,6,7,8,9 來說。假設要搜尋3

第一回和5比較,4<5。因此high變成4。中間值是2。

第二回和2比較,4>2。因此low變成3。中間值是3。

第三回和3比較,4>3。因此low變成4。中間值是4。

第四回和4比較,4=4。因此搜尋成功。

在最雖的情況下要4次。因為上面以4為例。可能會產生誤導以為最後一次比較是多餘。但若果是3.5便會顯示搜尋失敗﹐而此時便可看出worst case 是4。一般而言﹐worst case 是 log n = log 9 ~4

👍 0 👎 0

霹靂幽靈箭

2009-12-01 6:31 pm

嗯啊先找五，再找二，再找三，再找四
就是四次

👍 0 👎 0

[匿名]

2009-12-01 5:08 am

題目是最多次會是幾次

照你的方法這樣講
搜尋到第三次剩3跟4如果答案是3
那搜尋到4那時後
不是要再第四次的時候才會找到答案

參考: 自己:D

👍 0 👎 0

收錄日期: 2021-04-26 13:49:40
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20091130000015KK07393

檢視 Wayback Machine 備份