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

Видео на Vimeo

---

1.1 Определение линейного поиска

Линейный поиск (также известный как последовательный поиск) — это алгоритм поиска элемента в списке или массиве, который последовательно проверяет каждый элемент до тех пор, пока не найдёт совпадение или не проверит все элементы. Это самый простой алгоритм поиска, который не требует предварительной сортировки данных.

Основные принципы:

• Последовательная проверка: Алгоритм проходит по каждому элементу массива или списка, сравнивая его с искомым значением.
• Прекращение поиска: Поиск прекращается, когда найден элемент, соответствующий искомому значению, или когда все элементы проверены.
• Не требует сортировки: Линейный поиск может применяться к неотсортированным данным.
• Применение: Линейный поиск может применяться к любым структурам данных, которые поддерживают итерацию, включая списки и массивы.

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

Анализ временной сложности:

• Лучший случай (Best case): Элемент найден на первом месте, O(1).
• Средний случай (Average case): Элемент найден где-то в середине, O(n/2), что эквивалентно O(n).
• Худший случай (Worst case): Элемент найден на последнем месте или отсутствует, O(n).

1.2 Пошаговая реализация линейного поиска

Шаги линейного поиска:

• Инициализация: Установить начальный индекс для поиска (обычно нулевой индекс).
• Последовательная проверка: Проверять каждый элемент списка или массива на соответствие искомому значению.
• Условие завершения: Если элемент найден, вернуть его индекс. Если все элементы проверены и искомое значение не найдено, вернуть специальное значение (обычно -1 или None).

Реализация линейного поиска в Python:

def linear_search(arr, target):
    # Проходим по каждому элементу массива
    for index, element in enumerate(arr):
        # Если текущий элемент равен искомому значению, возвращаем его индекс
        if element == target:
            return index
    # Если элемент не найден, возвращаем -1
    return -1

Пошаговое объяснение реализации:

• Инициализация цикла: Используется цикл for с функцией enumerate, которая возвращает индекс и элемент массива на каждой итерации.
• Сравнение: На каждой итерации текущий элемент сравнивается с искомым значением (target).
• Возврат индекса: Если текущий элемент равен искомому значению, возвращается индекс этого элемента.
• Возврат -1: Если цикл завершился и искомый элемент не был найден, возвращается -1.

# Пример использования:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 7 найден на индексе 2

# Пример использования для элемента, которого нет в массиве:
target = 5
result = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {result}")  # Вывод: Элемент 5 найден на индексе -1

1.3 Примеры задач, решаемых с помощью линейного поиска

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

Задача 1: Поиск элемента в массиве

Нужно найти заданное число в массиве чисел.

Пример:

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Элемент {target} найден на индексе {index}")  # Вывод: Элемент 70 найден на индексе 3

Задача 2: Проверка наличия элемента в списке

Нужно проверить, присутствует ли заданное значение в списке строк.

Пример:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Элемент {target} {'найден' if found else 'не найден'}")  # Вывод: Элемент cherry найден

Задача 3: Поиск минимального или максимального элемента

Нужно найти минимальное или максимальное значение в списке.

Пример:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Минимальное значение: {min_value}")  # Вывод: Минимальное значение: 2

Задача 4: Поиск первого вхождения

Найти первое вхождение заданного элемента в списке.

Пример:

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Первое вхождение {target} на индексе {index}")  # Вывод: Первое вхождение 2 на индексе 1

Задача 5: Подсчёт количества вхождений

Подсчитать количество вхождений заданного элемента в списке.

Пример:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Элемент {target} встречается {count} раза")  # Вывод: Элемент 2 встречается 3 раза