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

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

Что такое алгоритм линейного поиска?

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

Предположим, что у нас есть список:

myList=[1,23,45,23,34,56,12,45,67,24]

Теперь мы хотим выполнить поиск по индексу элемента 12. Мы начнём с индекса 0 и проверим, присутствует ли там 12 или нет. Если да, мы вернём 0 в качестве результата или перейдем к индексу 1. Мы будем двигаться к индексу 6, где есть 12. После того как подтвердится, что 12 присутствует в индексе 6, мы выведем 6. Если какой-либо элемент отсутствует, мы вернем значение -1, которое укажет, что элемент отсутствует в списке.

Теперь давайте определим алгоритм для операции линейного поиска.

Алгоритм линейного поиска

Алгоритм линейного поиска может быть задан так:

Входные данные для алгоритма: список и элемент для поиска.

Вывод: индекс элемента, если он присутствует. В противном случае -1.

1. Начинаем с индекса 0.
2. Проверяем, присутствует ли элемент в текущей позиции.
3. Если да, выводим этот индекс.
4. Проверяем, последний ли это элемент списка.
5. Если да, выводим значение -1.
6. Переходим к следующему индексу.
7. Конец.

Так выглядит этот алгоритм в Python:

def LinearSearch(input_list: list, element: int):
    list_len = len(input_list)
    for i in range(list_len):
        if input_list[i] == element:
            return i
    return -1


myList = [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
print("Given list is:", myList)
position = LinearSearch(myList, 12)
print("Element 12 is at position:", position)

Вывод:

Given list is: [1, 23, 45, 23, 34, 56, 12, 45, 67, 24]
Element 12 is at position: 6

Недостатки алгоритма линейного поиска

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

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

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

Заключение

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