java - `if else` 和 `if-else if-else` 之间有区别吗？

Question

在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;  
}  

据称这是比传统教科书二分查找更好的版本，因为....算法每次迭代只使用一个条件分支
这是真的？我的意思是 if 指令在汇编中被翻译成 CMP 和 Branch 指令，所以我想不出 if-else 优于 if-else if-else
在高级语言中是否存在我应该考虑的差异？ “延迟”版本的代码在我看来更紧凑，但是在如何形成 if-else 语句方面是否有优化或惩罚？

Answer 1

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

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

1. 如果您要比较的只是两个整数，那么编译器可以检测到它可以只计算一次比较结果，然后同样评估采用哪个分支。
2. 二分搜索的复杂度为 O(logN)，因此即使要搜索的元素数量非常大，所采用的迭代次数实际上也非常少。您是否看到有什么不同是有争议的。
3. 现代 CPU 功能的实现，例如推测执行和分支预测(尤其是在“不错的”算法中，例如二分搜索)可能比这种优化具有更明显的效果(虽然我无法检查)。

注意事项:

¹ 其实是另一种等式比较移出时不需要检查的条件，但概念上没有区别。