algorithm - 执行二进制搜索

Question

我正在执行二进制搜索，假设我必须找到 x 的最小值，这样 black_box(x) 会给我 true 结果。

black_box(x)的属性

• 如果 black_box(x) 给出 true 那么 x+1,x+2,x+3,x+4....upto infinty 全部给我真

对于整数值，这是简单的二分搜索

 start=0;
 end = Max;
 ans=-1;
 while(start<=end){

    mid =(start+end)/2;
   if(black_box(mid)):
       end =mid-1
       ans=mid;
   else: start=mid+1;
}

如果我想要一个 float 整数到小数点后 2 位，我应该如何进行二进制搜索？

Answer 1

您只需迭代直到start 和end 相差不超过0.01。所以停止条件现在是:

while(end-start > 0.01){

此外，正如您自己在评论中指定的那样，您不能在算法中递增/递减 start 和 end，因为索引不是离散的。现在完整的算法是:

 start=0;
 end = Max;
 ans=-1;
 while(end-start > 0.01){

    mid =(start+end)/2.0;
   if(black_box(mid)):
       end =mid
       ans=mid;
   else: start=mid;
}

这是有效的，因为在每次迭代中，start 是精确值的下限，end 是上限 上的确切值。如果两者的差异不超过 0.01，我们知道它在 start 和 end 之间，并且由于差异小于 0.01，所以它精确到两位小数。

然而，从某种意义上说，您的算法是错误的，因为通过设置 end = Inf，您无法使用它。您或许可以使用最大可表示值，或者首先使用指数增量搜索作为预处理步骤。