Модификация бинарного поиска - PullRequest
Новая
       10

Модификация бинарного поиска

0 голосов
/ 12 марта 2019

Я пытался решить следующую проблему. У меня есть последовательность положительных целые числа, которые могут быть очень длинными (несколько миллионов элементов). это последовательность может содержать «скачки» в значениях элементов. Вышеупомянутый прыжок означает, что два последовательных элемента отличаются друг от друга более чем на 1.

Пример 01 :

1 2 3 4 5 6 7 0

В приведенном выше примере скачок происходит между 7 и 0.

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

Пример 02 :

9 1 2 3 4 6 7 8

Здесь первый прыжок между 9 и 1 - это обход. Второй прыжок между 4 и 6 - прыжок, который я ищу.

Моя идея состоит в том, чтобы как-то изменить алгоритм двоичного поиска, но я не уверен, возможно ли это из-за присутствия циклического поиска. Стоит сказать, что только два скачка могут произойти в максимуме, и между этими скачками элементы сортируются. У кого-нибудь есть идеи? Заранее спасибо за любые предложения.

1 Ответ

0 голосов
/ 12 марта 2019

Вы не можете найти эффективное решение (Эффективное, означающее не просмотр всех чисел, O (n)), так как вы не можете сделать вывод о своих числах, посмотрев на менее чем все.Например, если вы посмотрите только на каждое второе число (все еще O (n), но лучший коэффициент), вы пропустите двойной прыжок, как эти: 1 5 3.Вы можете и должны посмотреть на каждое число и сравнить его с соседями.Вы можете разделить свою рабочую нагрузку и использовать многоядерный подход, но это все.

Обновление

Если у вас есть особый случай, что в вашем списке только 1 прыжок иостальное отсортировано (например, 1 2 3 7 8 9), вы можете найти этот переход довольно эффективно.Вы не можете использовать ванильный бинарный поиск, поскольку список может быть отсортирован не полностью, и вы не знаете, какой номер вы ищете, но вы можете использовать сокращение экспоненциального поиска, которое имеет некоторое сходство.

Для работы этого алгоритма нам понадобятся следующие предположения:

  • Существует только 1 прыжок (я игнорирую «скачкообразный переход», поскольку он технически не существует между любыми следующими элементами)
  • Список отсортирован в противном случае, и он строго монотонно увеличивается

С этими допущениями мы теперь в основном ищем прерывание в нашей монотонности.Это означает, что мы ищем случай, когда 2 элемента и b имеют n элементов между ними, но не выполняют b = a + n.Это должно быть верно, если между двумя элементами нет перехода.Теперь вам нужно только найти элементы, которые не выполняют это нелинейным образом, отсюда и экспоненциальный подход.Этот псевдокод может быть таким алгоритмом: 

let numbers be an array of length n fulfilling our assumptions

start = 0
stepsize = 1
while (start < n-1)
    while (start + stepsize > n)
        stepsize -= 1
    stop = start + stepsize
    while (numbers[stop] != numbers[start] + stepsize)
        // the number must be between start and stop
        if(stepsize == 1)
            // congratiulations the jump is at start to start + 1
            return start
        else
            stepsize /= 2
    start += stepsize
    stepsize *= 2

no jump found
...