optimization - 比較数の観点からの二分探索の最適化

Question

最近、私はインタビューでこの質問をされました。二分探索では、2つの比較があります。1つは中間値よりも大きい値、もう1つは中間値よりも小さい値です。一度だけチェックする必要があるように最適化できますか？

Answer 1

いいえ、できません。演算子を切り替えることはできますが（たとえば、大小の代わりに大小を使用する）、2つの比較になります。二分探索では、実際には3つの結果があり、そのうちの2つを比較してもどちらも当てはまらない場合は、3番目の結果になります。

例えば：

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

演算子を切り替えると、関係する演算子が変わりますが、常に2つの比較が必要になります。

Answer 2

はい、いくつかの方法で。

一部のバージョンのFortranに存在する3者間比較を実行する（「算術IF」を参照）。

x86（およびその他）アセンブリでは、1つを使用できますcmpが、2つのブランチを使用できます。

同等性の遅延検出トリックを使用する。