optimization - 根据比较次数进行二分搜索优化

Question

最近我在一次采访中被问到这个问题。在二分搜索中，我们有两个比较，一个是大于，另一个是小于中间值。它可以以某种方式进行优化，以便我们只需要检查一次吗？

Answer 1

是的，在几个方面。

通过进行三路比较，这在某些版本的 Fortran 中存在（参见“算术 IF”）。

通过玩弄措辞 - 在 x86（和其他）程序集中，您可以使用一个cmp但仍然使用两个分支。

通过使用延迟检测相等技巧。

Answer 2

不，你不能。虽然您可以切换运算符（例如，而不是更大和更少使用更大和相等），但您最终会得到两个比较。在二分查找中，你实际上有三个结果，如果你比较其中两个结果都不是真的，那只能是第三个。

例如：

if (lookup < mid)
  searchLower();
else if (lookup > mid)
  searchUpper();
else
  found(lookup);

如果您切换运算符，所涉及的运算符将发生变化，但您始终需要进行两次比较。