0

我看过很多二分搜索的例子，很多方法如何优化它，所以昨天我的讲师写了代码（在这段代码中，我们假设第一个索引从 1 开始，最后一个索引是 N，所以 N 是数组的长度，考虑它在伪代码中。代码是这样的：

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 编写的，但是语言不依赖。

4

1 回答 1

1

这实际上取决于您是否找到该元素。如果你不这样做，这将保存一些比较。如果您可以在前几跳中找到元素，那么您就节省了所有后续比较和算术的工作。如果数组中的所有值都是不同的，那么很明显你不太可能在早期就找到正确的索引——但是如果你有大量包含相同值的数组，那会改变数学。

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

R:=m;

通常是

R:=m-1;

...尽管这很少会产生重大影响。

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

另一个好处是，如果元素不在数组中，则索引说明它的位置

无论您是否检查是否相等，这都是正确的。我见过的每个二进制搜索实现都会提供该信息。

于 2012-10-10T05:50:03.270 回答