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

Когда дело доходит до алгоритмов поиска, есть два алгоритма, которые довольно известны в сообществе программистов (например, линейный поиск и двоичный поиск).

Линейный поиск

Согласно Википедии, линейный поиск определяется следующим образом: «Линейный поиск или последовательный поиск — это метод поиска элемента в списке. Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или пока не будет просканирован весь список».

Сокращая простыми словами, вы начинаете со списка (индекс-0) и ищете один за другим, пока не найдете искомый элемент. Например, мне нужно найти 3 в списке [7,2,0,7,2,3,5,9,5]

начинаем с индекса 0,

3 присутствует в индексе-0 → NO,

3 присутствует в индексе-1 → NO,

3 присутствует в индексе-2 → NO,

3 присутствует в индексе-3 → НЕТ,

3 присутствует в индексе-4 → НЕТ,

присутствует 3 в index-5 → YES. STOP возвращает номер индекса, т. е. 5

В худшем случае номер, который вам нужно найти, может отсутствовать в списке. когда вы достигли конца списка, просто верните -1.

Давайте попробуем то же самое в коде Python.

def binary_searching(my_list, element):
    i = 0
    while i < len(my_list):
        if my_list[i] == element:
            return i
        i = i + 1
    else:
        return -1


if __name__ == "__main__":
    my_list = [7, 2, 0, 7, 2, 3, 5, 9, 5]
    element = 3
    idx = binary_searching(my_list, element)
    print(idx)

Временная сложность для линейного поиска составляет O(n), поскольку в худшем случае он перемещается по всему списку.

Сложность пространства для того же составляет O(1), так как она не занимает никакого места, кроме входного списка.

Бинарный поиск

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

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

Основываясь на начале и конце, мы находим mid = (start + end) / 2. Теперь мы сравниваем значение среднего индекса с элементом, который нужно найти.

Случай 1. Если значение в середине индекса равно элементу, мы просто возвращаем средний индекс.

Случай 2. Если значение в середине индекса больше, чем у элемента, скорректируйте значение end = mid — 1. Причина в том, что если значение в середине индекса больше, чем элемент, то все значение от среднего индекса до конечного индекса больше, чем элемент, который мы ищем. Таким образом, мы можем игнорировать эти индексы.

Случай 3: если значение в середине индекса меньше, чем у элемента, даже в этом случае нам нужно скорректировать значение start = mid + 1. Причина очевидна. Если значение среднего индекса меньше, то все значения ниже среднего индекса также меньше.

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

Код Python для двоичного поиска

def binary_searching(my_list, element):
    start = 0
    end = len(my_list) - 1
    while start <= end:
        mid = (start + end) // 2  # Integer Division
        if my_list[mid] < element:
            start = mid + 1
        elif my_list[mid] > element:
            end = mid - 1
        else:
            return mid  # my_list[mid] == element
    else:
        return -1


if __name__ == "__main__":
    my_list = [1, 4, 6, 8, 9, 10, 14, 17, 18]
    element = 19
    ans = binary_searching(my_list, element)
    print(ans)

Временная сложность для бинарного поиска составляет O(logn), так как для 100 элементов в списке мы итерируем только 6–8 элементов в цикле. Существуют математические выводы для этих временных сложностей, которые мы рассмотрим в следующих статьях.

Пространственная сложность O(1). Мы не создавали никаких структур данных, кроме переменных.

До скорой встречи с алгоритмами сортировки…