2

在WikiPedia文章中，Binary Search有一个名为的部分Deferred detection of equality提供了一种“优化”的二进制搜索版本，如下所示：

int binary_search(int A[], int key, int imin, int imax)  
{  
  while (imax > imin)  
  {  
    int imid = (imin + imax) / 2;  
    if (A[imid] < key)  
      imin = imid + 1;  
    else  
      imax = imid;  
  }  
  if((imax == imin) && (A[imin] == key))  
    return imin;  
  else  
    return KEY_NOT_FOUND;  
}

据称这是比传统教科书二进制搜索更好的版本，因为这.... algorithm uses only one conditional branch per iteration
是真的吗？我的意思是if指令被翻译成汇编指令CMP，Branch所以我不认为 anif-else比 an 更好if-else if-else
是否存在这样的差异，我应该在更高级别的语言中考虑到这一点？if-else我管理“延迟”版本的代码似乎更严格，但是您如何形成语句有优化或惩罚吗？

4

1 回答 1

3

关键概念是每次迭代使用较少的条件。也就是说，相等检查已移到while循环之外，因此它只运行一次，而在基本版本中，每次都需要检查¹。

也就是说，我不确定在使用优化形式时是否真的会有可测量的差异。例如，考虑一下：

  1. 如果您要比较的只是两个整数，那么编译器可以检测到它可以只计算一次比较结果，然后评估要采用哪个分支。
  2. 二进制搜索是 O(logN)，因此即使要搜索的元素数量很大，所进行的迭代次数实际上也会非常少。你是否会看到任何不同是有争议的。
  3. 现代 CPU 功能的实现，例如推测执行和分支预测（特别是在像二进制搜索这样的“好”算法中）可能比这种优化具有更明显的效果（尽管我不知道）。

笔记：

¹ 实际上，当相等比较移出时，这是另一个不需要检查的条件，但从概念上讲没有区别。

于 2012-04-25T15:45:57.183 回答