Линейный поиск элемента массива

Что такое линейный поиск?

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

Реализация на Python

Функция линейного поиска

def linear_search(arr, target):
    """
    Линейный поиск элемента в массиве
    
    Args:
        arr: массив для поиска
        target: искомый элемент
    
    Returns:
        индекс элемента или -1, если не найден
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Элемент найден
    return -1  # Элемент не найден

# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
search_value = 22

result = linear_search(numbers, search_value)
if result != -1:
    print(f"Элемент {search_value} найден на позиции {result}")
else:
    print(f"Элемент {search_value} не найден")

Анализ сложности

Временная сложность

  • Лучший случай: O(1) - элемент найден на первой позиции
  • Средний случай: O(n/2) - элемент найден в середине массива
  • Худший случай: O(n) - элемент не найден или находится в конце

Пространственная сложность

  • O(1) - используется только одна переменная для индекса
  • Алгоритм не требует дополнительной памяти

Где используется линейный поиск?

Применение алгоритма

  • Небольшие массивы - когда количество элементов невелико
  • Неотсортированные данные - когда массив не упорядочен
  • Поиск по одному критерию - простые условия поиска
  • Образовательные цели - изучение основ алгоритмов
  • Прототипирование - быстрая реализация для тестирования

Визуализация процесса поиска

Поиск элемента 22 в массиве [64, 34, 25, 12, 22, 11, 90]

64
34
25
12
22
11
90

Результат: Элемент 22 найден на позиции 4 (индекс 4)

Альтернативные способы реализации

С использованием enumerate()

def linear_search_enumerate(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

С использованием list.index()

def linear_search_index(arr, target):
    try:
        return arr.index(target)
    except ValueError:
        return -1

Рекурсивная версия

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):
        return -1
    if arr[index] == target:
        return index
    return linear_search_recursive(arr, target, index + 1)