0

私のバイナリ検索は、std::vector. しかし、その位置を見つけるには 1 つ (またはそれ以上?) の比較を実行しているように思えます。特に最後の三項。私はこれを間違って設計しましたか？明確にするために、出力のエラーに気づいていません。

template<typename T>
size_t find(std::vector<T> data, T value) //returns position value should be inserted at
{
 size_t start = 0;
 size_t end = data.size();

 if (!end) return 0;

 size_t diff;

 while (diff = (end - start) / 2)
 {
  size_t mid = diff + start;

  if (data[mid].value <= value)
  {
   start = mid;
  }
  else
  {
   end = mid;
  }
 }

 return data[start].value <= value ? end : start;
}
4

1 に答える 1

1

二分探索では、基本的に 、 、および の 3 方向の分岐 >が<あり=ます。これを C++ で 2 つの比較演算子なしで記述する方法はありませんが、まともなコンパイラであれば、それらを比較のために 1 つのマシン命令に最適化し、その後に結果に対して 2 つの条件付き分岐を行うことを期待しています。

于 2013-01-28T16:43:45.037 に答える