Блог

Главная - Вопросы по программированию - Поиск в циклическом массиве

Поиск в циклическом массиве

#arrays #binary-search #circular-buffer

#массивы #двоичный-поиск #циклический буфер

Вопрос:

Каков наилучший способ поиска в циклическом массиве?

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

Является ли бинарный поиск правильным подходом для начала?

Комментарии:

1. двоичный поиск требует, чтобы данные были уже упорядочены…

2. и как вы определяете «лучший»?

3. Циклический массив — это, по сути, линейный массив с ограниченным размером, так как бы вы сортировали на месте с помощью линейного массива? Как упоминал @MitchWheat, необходимо определить наилучший способ.

Ответ №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;       
}