arrays - 円形配列で検索

Question

円形配列を検索する最良の方法は何ですか?

Example 1  array : 45 67 44 11 49 4 56 12 39 90
           circular array 11, 49, 4, 56, 12, 39, 90, 45, 67

二分探索は最初から正しいアプローチですか?

Answer 1

これと同じ問題があり、検索を 2 回実行せずに組み込み関数を使用する方法が見つからなかったため、カスタム関数を作成しました。

範囲外のチェックをより迅速に行う方法はおそらくありますが、これは私の目的に役立ちます。(消費者がそれを循環バッファー上の実際のインデックスに変換し直すのは苦痛だったので、負のインデックスのものを使用して標準のバイナリ検索インターフェイスをコピーしたくありませんでした)

public bool BinarySearchCircular<T>(T[] array, T searchValue, int head, out int lowerIndex, out int upperIndex) where T : IComparable<T>
{
  int bottom = 0;
  int top = (int)array.Length - 1;
  int count = (int)array.Length;
  int middle = top >> 1;
  while (top >= bottom)
  {
      int middleIndex = (middle + head) % count;
      if (array[middleIndex].CompareTo(searchValue) == 0)
      {
          upperIndex = middleIndex;
          lowerIndex = middleIndex;
          return true;
      }
      else if (array[middleIndex].CompareTo(searchValue) > 0)
      {
          top = middle - 1;
      }
      else
      { 
          bottom = middle + 1; 
      }
      middle = (bottom + top) >> 1;
  }
  if(array[head].CompareTo(searchValue) < 0)
  {
    lowerIndex = head;
    upperIndex = -1;
  }
  else if(array[(head+1) % count].CompareTo(searchValue)  > 0)
  {
    upperIndex = (head+1) % count;
    lowerIndex = -1;
  }
  else
  {
    lowerIndex = (top + head) % count;
    upperIndex = (bottom + head) % count;
  }

  return false;       
}

Answer 2

二分探索は、配列がソートされている場合にのみ役立ちます。

問題のドメインについて多くの情報を提供しませんでしたが、1 つのアプローチは、セット (またはハッシュ テーブル) を使用することです。配列に入れるすべての数値について、セットにも挿入します。セット (またはハッシュ テーブル) 内の検索は一定時間で行われるため、「検索」はありません。配列からアイテムを削除するときは、セットからも削除してください。循環バッファーがいっぱいになると値が上書きされる場合は、上書きされた値を削除するようにセットも更新するようにしてください。

別のデータ構造を使用できない場合、できる最善の方法は、配列の線形スキャンです。