Линейный поиск — это простейший алгоритм поиска элемента в последовательности. Он последовательно проверяет каждый элемент, пока не найдет нужный или не пройдет весь список.

Сложность алгоритма

  • В худшем случае: O(n) — если элемент отсутствует или находится в конце списка.

  • В среднем случае: O(n/2) — элемент может быть найден как в начале, так и в середине последовательности.

  • В лучшем случае O(1) - если элемент нашелся первым. 

Таким образом, время выполнения линейно зависит от размера данных: чем больше список, тем дольше поиск.

Пример реализации на Python

from random import randint
searching_item = 7
sequence = [randint(1, 10) for _ in range(10)]
for item in sequence:
   if item == searching_item:
       print("Элемент найден!")
       break

Проверка средней сложности

from random import randint

searching_item = 7
attempts = []

for _ in range(10):
   sequence = [randint(1, 10) for _ in range(10)]
   found = False
   
   for index, item in enumerate(sequence, start=1):
       if item == searching_item:
           attempts.append(index)
           found = True
           break
   
   if not found:  # Если элемент не найден, добавляем длину списка
       attempts.append(len(sequence))

average_attempts = sum(attempts) / len(attempts)
print(f"Среднее количество проверок: {average_attempts}")

 

Пояснение к коду:

  1. Генерируем случайную последовательность и ищем в ней число 7.

  2. Если элемент найден, записываем количество попыток.

  3. Если элемент отсутствует, добавляем длину списка (максимальное число проверок).

  4. Выводим среднее значение попыток.

Результат:
При многократном запуске среднее число проверок будет около n/2, что подтверждает теорию.

Линейный поиск прост в реализации, но неэффективен для больших данных. Для ускорения работы с отсортированными массивами лучше использовать бинарный поиск (O(log n)), а для частых запросов — хэш-таблицы (O(1)).