二進制搜索在這種情況下不起作用？

https://leetcode.com/problems/guess-number-higher-or-lower-ii/#/description。二進制搜索在這種情況下不起作用？

我們玩猜猜遊戲。遊戲如下：

我從1到n挑選一個數字。你必須猜測我挑選了哪個號碼。

每當你猜錯了，我會告訴你我選擇的號碼是高還是低。

但是，當您猜測某個特定的數字x，並且您猜錯了時，您支付$ x $ 。當你猜測我選擇的數字時，你贏得比賽。

給定一個特定的n≥1，找出多少錢（至少），你需要有保證勝利。

我正在練習這個問題。我認爲這個問題可以使用二進制搜索來解決。特別是，對於最壞的情況，數字總是可以假定位於每個分割的右半部分。

例如：說n = 5。那麼你有

[1,2,3,4,5]。

第一次嘗試= 3，然後第二次嘗試= 4.這會給你一個7美元的最壞情況。但我已經看過解決方案，在我看來，他們都使用動態編程。我想知道二進制搜索算法在這種情況下怎麼不起作用？

來源

2017-05-09 wrek

看起來問題的措辭有些不一致。你有沒有檢查[此澄清]（https://discuss.leetcode.com/topic/68252/clarification-on-the-problem-description-problem-description-need-to-be-updated/2）？ –

通過二進制搜索，您可以找到最少的轉數你需要採取找到號碼。但是，在這個問題上，你必須考慮成本並不number of turns而是min sum that you pay in worst case這是由部分if you guess wrong, you pay $x

這裏定義是哪裏做的二進制搜索將無法正常工作的例子：

[1,2,3 ，4]

在最壞的情況下

pick(2) -> decision: target is bigger 
-> pick(3) -> decision: target is bigger [if decision is smaller thats not worst case] 
-> pick(4) -> done 

Total cost = 2+3 = 5

使用BS在最佳策略：

pick(3) -> decision: smaller [if decision is bigger thats not worst case] 
-> pick(1) -> decision: bigger [if decision is smaller thats not worst case] 
-> pick(2) -> done 

Total cost = 3+1 = 4

因此，對於最佳策略，您需要考慮動態編程解決方案。既然你的問題是爲什麼二進制搜索不在這裏作爲最佳策略，我會留下我的答案，直到這只是一個例子，並沒有描述DP解決方案。

來源

2017-05-09 06:49:30

這可能有些幫助。二進制搜索應該可以工作。

public int guessNumber(int n) 
{ 
    int low=1; 
    int high=n; 

    while(low <= high){ 
     int mid = low+((high-low)/2); 
     int result = guess(mid); 
     if(result==0) 
     { 
      return mid; 
     } 
     else if(result==1) 
     { 
      low = mid+1; 
     } 
     else 
     { 
      high=mid-1; 
     } 
    } 

return -1; }

來源

2017-05-09 06:49:41 rachitmanit

你的問題並不適用於二進制搜索，因爲一個大因素 - 二進制搜索的設計專注於減少你需要找到特定數量的嘗試次數。

二進制搜索只是最大限度地減少找到你的號碼所需的命中數量（不依賴於你打的值）。它不能最小化任何其他因素。

所以，如果你想找到最低$（你打的數字的總和），你必須支付你最好建議使用動態編程。

來源

2017-05-09 07:01:43

二進制搜索在這種情況下不起作用？

回答

相關問題