二进制搜索在这种情况下不起作用？

Question

https://leetcode.com/problems/guess-number-higher-or-lower-ii/#/description.

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Given a particular n ≥ 1, find out how much money (at minimum) that you need to have to guarantee a win.

我正在练习这道题。我认为这个问题可以使用二进制搜索来解决。特别地，对于最坏的情况，数字总是可以假设位于每个分裂的右半部分。

示例：假设 n=5。那么你有

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

First try= 3， Then second try = 4. 这会给你最坏的情况7美元。但是我看了解决方案，在我看来他们都使用动态规划。我想知道为什么二进制搜索算法在这种情况下不起作用？

Answer 1

使用二进制搜索，您可以找到找到数字所需的最少转数。但是在这个问题中，您必须考虑的成本不是 number of turns 而是 min sum that you pay in worst case ，它由 if you guess wrong, you pay $x

部分定义

这是一个二分查找不起作用的例子：

[1,2,3,4]

在最坏的情况下使用 BS

   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

在最优策略中：

   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 解决方案。

Answer 2

这可能会有帮助。二进制搜索应该工作。

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; }

Answer 3

您的问题不适用于二进制搜索，因为一个重要因素 - 二进制搜索的设计重点是减少查找特定数字所需的尝试次数。

二分搜索只是最小化查找数字所需的命中次数（不依赖于你命中的值）。它不能最小化任何其他因素。

因此，如果您想找到您必须支付的最低 $（您所击中的数字总和），最好使用动态编程。

二进制搜索在这种情况下不起作用？

Binary Search Doesn't work in this case?

algorithm

binary-search

minimax