Бинарный поиск с двумя средними (два указателя) одновременно - PullRequest
Новая
       4

Бинарный поиск с двумя средними (два указателя) одновременно

0 голосов
/ 16 апреля 2020

Просто я хочу разделить мой массив на три подмассива, а не на два, это логично? И, пожалуйста, помогите мне понять этот алгоритм и написать его 

def contains(elements, value):
left, right = 0, len(elements) - 1

if left <= right:
    middle = (left + right) // 2

    if elements[middle] == value:
        return True

    if elements[middle] < value:
        return contains(elements[middle + 1:], value)
    elif elements[middle] > value:
        return contains(elements[:middle], value)

return False

1 Ответ

0 голосов
/ 16 апреля 2020

Вы действительно можете адаптировать бинарный поиск для разделения массива на несколько разделов, а не только на два. В более общем смысле, вот идея, лежащая в основе k-арного поиска:

  • Разделить массив на k секций примерно одинакового размера. (Для двоичного поиска это две половины. Для вашего поиска это будет три трети)

  • Выберите последний элемент первых (k-1) разделов для использования в качестве ключей. (Для двоичного поиска вы выбираете последний элемент первой половины, средний элемент. Для вашего поиска это будут элементы в точках 1/3 и 2/3 в массиве.)

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

Что касается того, является ли это хорошей идеей - это очень хорошо может быть хорошей идеей! В k-арном поиске вы продолжаете уменьшать массив с коэффициентом k на каждой итерации, поэтому будет примерно лог k n = (log n) / (log k) итераций алгоритма. Каждая итерация рассматривает k - 1 ключи, поэтому вы выполняете O (k) работу. Это означает, что проделанная работа является O ((k / log k) n). Количество k / log k сводится к минимуму, когда вы выбираете k = e (то есть около 2.7182828), поэтому выбор k = 2 или k = 3 - хороший выбор. Однако из-за того, как работают процессорные кеши, я подозреваю, что выбор k = 2 будет быстрее в целом, потому что будет меньше пропусков кеша. (И эй! На практике мы склонны использовать бинарный поиск, так что это, вероятно, неплохая идея.)

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

Надеюсь, это поможет!

...