Re: [問題] 一個很像binary search的演算法， …

[Hatred (yo)]

※ 引述《mqazz1 (無法顯示)》之銘言：
: suppose that you are go guess the price of a commodity without knowing its price in advance,
: how fast can you guess its price,
: assuming the real price of the commodity is n.
: use less than O(n) comparisons.
: 如果這是運用到binary search的觀念
: 我記得binary search好像是O(logn)
: 那我先從比n大的數開始開始猜
: 之後每次都取它的中間數猜下去..應該就可以在O(n)內猜到
: 可是題目一開始說 不知道商品的價格
: 那應該就沒辦法一開始就先猜到比n大的數..
: 請問這題可以運用到binary search的觀念嗎?
: 那我的想法應該要怎麼改進呢?
: 謝謝

其實我不是很懂題目的意思 :)

我猜 price 應該是一正整數吧 (否則如果是任意實數, 好像會沒辦法找),
可能可以這樣做:

先猜 price 是 1, 看看是剛好/過高/過低, 假設 (例如) 現在是過低好了, 那就猜 2,
假如還是過低, 我們就猜 4, 假設仍然過低, 我們就猜 8, 接著就是 16, 32, ... 一直
跑下去...

這樣一直猜到過高為止, 只猜了 O(log n) 次; 第一次過高時, 所猜的數字應不大於 2n,
所以之後就在 1 到 2n 之間用 binary search 再猜 O(log n) 次得到答案應該就行了.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.90.239
推 LPH66:其實不用 1~2n...最後一次如果是 2^k 則在 2^(k-1) 到 2^k
→ LPH66:之間二分搜即可  這一段只有 2^(k-1) 個數所以是 O(k)
→ LPH66:當然因為 n < 2^k < 2n 所以也是 O(log n) 啦...
推 FRAXIS:原題目也沒說會回答 過高/過低 如果只會回答 對/錯 怎解？
→ Hatred:只回答對錯的話, 就不會有 o(n) 的問法囉 :)
→ Hatred:不過我不是很確定題目的意思...
推 cibs:從 1 問到 n 不就是 O(n) 嗎？
→ Hatred:是的, 不過原題目看起來又有點像要 o(n) (而非 O(n)) 的方
→ Hatred:法 (是嗎, 其實我不是很確定, 另外就是每次是不是可以知道
→ Hatred:過高/過低 也不確定... 總之題目我看不太懂)