Sentinel Поиск в Python – Простое объяснение

Sentinel Search – это алгоритм поиска для списка элементов, которые хранятся последовательно. В этом руководстве мы изучаем, как работает алгоритм, мы будем сравнивать его с линейным поиском, и мы будем использовать алгоритм, чтобы увидеть, если он работает.

Предварительный реквизит: линейный поиск

Прежде чем перейти к поисковому поиску Sentinel, нам нужно понять, почему он существует, и делать то, что нам нужно сначала понять линейный поиск.

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

В этом процессе мы делаем два сравнения в каждой итерации. Первое сравнение – если список окончен или нет, а второй – это если текущий элемент соответствует целевой цене или нет. Но что, если произошел способ сократить эти сравнения, чтобы сделать поиск быстрее? Вот что намеревается поиск Sentinel.

Что такое Sentinel Search?

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

В Sentinel Search мы впервые вставляем цель в конце списка, а затем сравниваем каждый элемент списка, пока мы не найдем необходимый элемент. Либо требуемый элемент находится в списке, в этом случае он будет найден до достижения конца списка. Или список не имел цели, поэтому алгоритм достигнет конца списка и найдет целевой элемент, который мы вставили.

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

Наконец, мы можем проверить, был ли продукт, который мы нашли, было уже там или было добавлено нами. Эта проверка произойдет только один раз, и все время выполнения алгоритма будет значительно сокращена, потому что у нас есть еще одно сравнение для каждой итерации цикла.

Реализация Sentinel Search в Python

Давайте посмотрим Sentinel поиск, написанные в Python:

def sentinel(lst, target):
    size = len(lst)
    lst.append(target)
    i = 0
    while(lst[i] != target):
        i += 1
    if(i == size):
        return None
    else:
        return i

В приведенном выше коде мы начинаем получить размер списка, а затем добавить цель в конце списка.

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

В конце концов, мы проверяем, закончится ли он на последнем элементе или нет. Если да, то цель не присутствует в списке, в противном случае она есть. И мы возвращаем соответствующее значение соответственно.

Выход

Давайте попробуем запустить код и посмотреть, как он работает:

Заключение

В этом руководстве мы увидели, что такое поиск Sentinel, почему мы его используем, как он отличается от линейного поиска, его реализации в Python и, наконец, его вывод.

Надеюсь, у вас было отличное время обучения и увидимся в следующем руководстве.