Binary Search Doesn't work in this case?

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.

I was practicing this problem. I thought this problem can be solved using binary search. In particular, for the worst case, the number can always be assumed located at 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 a worst case of 7 dollars. But I have looked at the solutions, it seems to me that they all use dynamic programming. I am wondering how come the binary search algorithm doesn't work in this case?

Answer 1

With Binary search you can find out min number of turns you need to take to find the number. But in this question the cost you have to think about is not number of turns but rather min sum that you pay in worst case which is defined by the part if you guess wrong, you pay $x

Here is an example where doing binary search will not work:

[1,2,3,4]

Using BS in 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 the optimum 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

So for the optimum strategy you need to think of a dynamic programming solution. Since your question is why binary search is not working here as best strategy, I will leave my answer upto this only showing an example and not describe the DP solution.