二进制搜索在这种情况下不起作用? [英] Binary Search Doesn't work in this case?

问题描述

https://leetcode.com/problems/猜测数字更高或更低的ii/#/说明.

我们正在玩猜猜游戏.游戏如下:

我选择一个从1到n的数字.你得猜猜我选了哪个号码.

每次您猜错了，我都会告诉您我选的号码是否更高或更低.

但是，当您猜出某个特定的x时，如果您猜错了，您支付$ x.当您猜到我选的号码时，您就赢了游戏.

给定一个特定的n≥1，请找出您至少需要多少钱才能保证获胜.

我正在练习这个问题.我认为可以使用二进制搜索解决此问题.特别是，在最坏的情况下，始终可以假设该数字位于每个拆分的右半部分.

示例:说n = 5.然后，您有

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

第一次尝试= 3，然后第二次尝试=4.这将给您带来7美元的最坏情况.但是我看过这些解决方案，在我看来它们都使用动态编程.我想知道为什么二进制搜索算法在这种情况下不起作用?

解决方案

通过二进位搜索，您可以找到需要转的最小转数.但是在这个问题中，您要考虑的成本不是匝数，而是在最坏情况下您支付的最低金额(由部分 if定义)您猜错了，您需要支付$ x

以下是无法执行二进制搜索的示例:

[1,2,3,4]

在最坏的情况下使用BS

  pick(2)->决定:目标更大->选择(3)->决策:目标更大[如果决策较小，那不是最坏的情况]->选择(4)->完毕总费用= 2 + 3 = 5 

在最佳策略中:

  pick(3)->决定:较小[如果决定较大，那不是最坏的情况]->选择(1)->决定:更大[如果决定较小那不是最坏的情况]->选择(2)->完毕总费用= 3 + 1 = 4 

因此，为了获得最佳策略，您需要考虑一种动态编程解决方案.由于您的问题是为什么二进制搜索不能在此作为最佳策略，因此我将仅给出一个示例，而不是描述DP解决方案.

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?

解决方案

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.

这篇关于二进制搜索在这种情况下不起作用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！