优化的二进制搜索

Question

我见过很多二进制查找的例子，很多方法如何优化它，所以昨天我的讲师写了代码(在这个代码中，让我们假设第一个索引从1开始，最后一个是N，所以N是数组的长度，考虑它在伪code.code中是这样的：

L:=1;
R:=N;
while( L<R)
{
m:=div(R+L,2);
 if A[m]> x
{
 L:=m+1;

}
else
{
 R:=m;

}
}

这里我们假设数组是A，所以讲师说我们不会浪费时间来比较元素是否每次都在数组中间部分，还有一个好处是，如果元素不在数组中，index表示它将位于何处，所以它是最优的，对吗?我的意思是，我见过John Bentley的许多种二进制搜索，例如(编程珍珠)等等，这段代码真的是最优的吗?在我的例子中，它是用pascal编写的，但语言不依赖。

Answer 1

这真的取决于你是否找到了元素。如果您不这样做，这将保存一些比较。如果您可以在前两个跃点中找到元素，那么您就省去了后面所有比较和算术的工作。如果数组中的所有值都是不同的，显然不太可能在早期命中正确的索引-但如果数组中包含相同值的大片区域，这将改变数学。

这种方法还意味着您不能像使用其他方法那样缩小范围-这是：

R:=m;

通常是

R:=m-1;

..。尽管这几乎不会产生显着的差异。

重要的一点是，这不会改变算法的整体复杂度-它仍然是O(log )。

索引的另一个好处是，如果元素不在数组中，

会指出它应该位于的位置

无论你是否检查是否相等，这都是正确的。我见过的每一个二进制搜索实现都会给出这个信息。