Находить предмет в круговой очереди?

Question

У меня круговая очередь заказанных товаров. Я хочу знать, есть ли в нем элемент со значением «х».

Каков наилучший способ (алгоритм) для этого?

Answer 1

Если вы можете получить доступ к каждому элементу по индексу, вы можете использовать двоичный поиск.

Если вы видите только первый элемент, вам нужно вытолкнуть его из очереди, пока ключ поиска не окажется ниже ключа элемента, который вы только что извлекли. Поскольку очередь отсортирована, вы можете остановиться, как только узнаете, что ключ больше не может находиться в очереди.

[РЕДАКТИРОВАТЬ] Поскольку вы можете получить доступ по индексу: деформируйте круговую очередь в объекте, который отображает его в «массив» (т. Е. С помощью метода get(index), где index работает от 0 до length-1 и что внутренне делает ((index+start)%length).

Таким образом, вы можете применить бинарный поиск, не задумываясь о фактической структуре данных.

Answer 2

«Наилучший» - это субъективный термин, а циклические очереди редко бывают достаточно большими, чтобы оправдать двоичный поиск, поэтому я бы выбрал простоту в отсутствие информации о размере очереди. Самый простой способ - просто начать с головы и проверять каждый элемент до конца (или вы прошли за ним в порядке), чтобы увидеть, существует ли он.

Допустим, переменная вашей головы указывает на первый элемент, который будет удален, а хвост указывает на следующее место для размещения элемента. Далее предположим, что вы тратите впустую слот предмета, чтобы упростить код (хитрость, чтобы упростить код и показать разницу между пустой и полной очередью). Это означает, что пустая очередь обозначается tail == head.

ptr = head
while ptr != tail:
    if element[ptr] = searchvalue:
        return true
    if element[ptr] > searchvalue:
        return false
    ptr = (ptr + 1) % queuesize;
return false

Answer 3

У OP, я подозреваю, есть круговой буфер фиксированного размера. Два условия поиска происходят.

Один, когда буфер заполняется, и один, когда буфер заполняется, где произошла перестановка и происходит перезапись предыдущих хранилищ.

Первый случай - это линейный поиск с начальным «интервалом» в нуле и, по-видимому, конечным интервалом записывается / поддерживается.

Второй случай сложнее. Начальный слот циркулирует, так как предыдущие хранилища перезаписаны. Конечный слот также циркулирует, только одна позиция после начального слота.

Чтобы выполнить линейный поиск по этим движущимся индексам, необходим перевод, чтобы поместить нулевой начальный слот и размер буфера конечного слота.

Как работает этот алгоритм, еще предстоит определить.

Answer 4

мы можем пройти в противоположном направлении? то есть от хвоста до головы. если так, то мы можем спроектировать что-то, что может использовать это. т.е. решить, каким образом продолжить поиск.

Так как он упорядочен, мы можем угадать его положение (просто угадать или, возможно, использовать статистику, если она доступна), а затем начать полный поиск только в том направлении, которое даст результат за меньшее количество попыток