Binary Search Doesn't work in this case?

Question

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

We play the Guess Game. The game is as follows:

I choose a number from 1 to n. You have to guess which number I chose.

Each time you make a mistake, I will tell you if the number I chose was higher or lower.

However, when you guess a certain number x and you are wrong, you pay $ x. You win the game when you guess the number I chose.

Given a specific n ≥ 1, find out how much money (at least) you need to guarantee victory.

I dealt with this problem. I thought this problem could be solved using binary search. In particular, for the worst case, the number can always be assumed to be in the right half of each split.

Example: say n = 5. Then you have

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

First try = 3, Then second try = 4. This will give you the worst case of $ 7. But I looked at the solutions, it seems to me that they all use dynamic programming. I am wondering why the binary search algorithm does not work in this case?

Answer 1

With binary search, you can find out the minimum number of turns you need to take in order to find the number. But in this matter, the value that you should think about is not number of turns, but rather min sum that you pay in worst case, which is determined by partif you guess wrong, you pay $x

Here is an example where binary search will not be performed:

[1,2,3,4]

Using BS in the worst case

   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

In an optimal strategy:

   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

- . , .

, , ( , ). .

, $( , ), , .