我正在练习这个问题。我认为可以使用二进制搜索解决此问题。特别是，在最坏的情况下，始终可以假设该数字位于每个拆分的右半部分。
例如:说n = 5。那你有
[1、2、3、4、5]。
第一次尝试= 3，然后第二次尝试=4。这将给您带来7美元的最坏情况。但是我看过这些解决方案，在我看来它们都使用动态编程。我想知道为什么二进制搜索算法在这种情况下不起作用？
最佳答案
通过二进制搜索，您可以找到需要转的最小转数。但是在这个问题中，您需要考虑的成本不是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解决方案。