Как лучше всего искать в круговом массиве?
Example 1 array : 45 67 44 11 49 4 56 12 39 90
circular array 11, 49, 4, 56, 12, 39, 90, 45, 67
Подходит ли двоичный поиск для начала?
Как лучше всего искать в круговом массиве?
Example 1 array : 45 67 44 11 49 4 56 12 39 90
circular array 11, 49, 4, 56, 12, 39, 90, 45, 67
Подходит ли двоичный поиск для начала?
Двоичный поиск полезен только в том случае, если массив отсортирован.
Вы не предоставили много информации о проблемной области, но одним из подходов было бы использование набора (или хеш-таблицы). Для каждого числа, которое вы вводите в массив, также вставляйте его в набор. Поиск в наборе (или в хеш-таблице) происходит в постоянное время, поэтому «поиск» отсутствует. Когда вы удаляете элемент из массива, также удаляйте его из набора. Если ваш кольцевой буфер перезаписывает значения при заполнении, убедитесь, что он также обновляет набор, чтобы удалить перезаписанные значения.
Если вы не можете использовать другую структуру данных, лучшее, что вы можете сделать, - это линейное сканирование массива.
Была такая же проблема, не было возможности использовать встроенные функции без двойного выполнения поиска, поэтому написал собственный.
Вероятно, есть способ быстрее выполнить проверку вне диапазона, но это служит моей цели. (Я не хотел копировать стандартный интерфейс двоичного поиска с отрицательным индексом, поскольку преобразование потребителя обратно в реальные индексы в кольцевом буфере было бы болезненным)
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;
}