二進制搜索優化的比較數量方面

Question

最近我在一次採訪中被問到了這個問題。 在二進制搜索中，我們有兩個比較大於一個和小於中間值的其他比較。它是否可以進行優化，以便我們只需檢查一次？

Answer 1

是的，有幾種方式。

通過進行三方比較，其中存在一些Fortran版本（請參閱「算術IF」）。

通過在x86（和其他）程序中玩弄技巧 - 可以使用一個cmp，但仍使用兩個分支。

通過使用Deferred Detection of Equality技巧。

Answer 2

不，你不能。雖然您可以切換操作員（例如，而不是更大和更少使用更大和相等），您將最終得到兩個比較。在二分法搜索中，實際上有三個結果，如果您比較其中兩個結果並且兩個結果都不是真的，則它只能是第三個結果。

例如：

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

如果您切換周圍的運營商而言，牽連一會改變，但你總是需要兩個comparisions。