Практическая работа 1 пара

Практическое занятие №2 «Оценка сложности алгоритмов поиска»

Практическое сравнение линейного и бинарного поиска.

Цель работы

Сравнить линейный и бинарный поиск, посчитать число сравнений и увидеть, почему требование «массив должен быть отсортирован» принципиально для бинарного поиска.

Короткая теория

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

Бинарный поиск на каждом шаге отбрасывает примерно половину оставшегося диапазона. Для отсортированного массива его худшая временная сложность — O(log n).

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

Исходный код

Создайте файл search_complexity.py:

from timeit import repeat


def linear_search(a, target):
    comparisons = 0

    for i, value in enumerate(a):
        comparisons += 1

        if value == target:
            return i, comparisons

    return -1, comparisons


def binary_search(a, target):
    left = 0
    right = len(a) - 1
    comparisons = 0

    while left <= right:
        mid = (left + right) // 2
        comparisons += 1

        if a[mid] == target:
            return mid, comparisons

        if a[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1, comparisons


def measure(func, a, target):
    times = repeat(
        lambda: func(a, target),
        repeat=5,
        number=100
    )
    return min(times) / 100


sizes = [10, 100, 1000, 100000]

for n in sizes:
    data = list(range(n))

    tests = {
        "первый": 0,
        "середина": n // 2,
        "последний": n - 1,
        "нет в массиве": n + 1,
    }

    print(f"\nРазмер массива: {n}")

    for label, target in tests.items():
        _, lin_cmp = linear_search(data, target)
        _, bin_cmp = binary_search(data, target)

        lin_t = measure(linear_search, data, target)
        bin_t = measure(binary_search, data, target)

        print(
            f"{label:13} | "
            f"linear: {lin_cmp:7} сравн., {lin_t:.8f} c | "
            f"binary: {bin_cmp:3} сравн., {bin_t:.8f} c"
        )

Ход работы

Запустите программу и проверьте результаты для размеров 10, 100, 1000 и 100000.
Для каждого размера зафиксируйте число сравнений при поиске:
- первого элемента;
- элемента из середины;
- последнего элемента;
- значения, которого в массиве нет.
Для бинарного поиска сравните полученное число сравнений с оценкой log₂(n).
Измените массив на [7, 2, 9, 1, 5, 3, 8] и попробуйте найти значения бинарным поиском. Объясните, почему результат может быть неверным.
Отсортируйте этот массив и повторите поиск.

n	Цель поиска	Линейный: сравнений	Бинарный: сравнений	Вывод
10	последний
100	последний
1000	последний
100000	последний
100000	нет в массиве

Задания для анализа

Какой поиск выгоднее для одного маленького неотсортированного списка?
Почему бинарный поиск ускоряется не «в два раза», а меняет сам характер роста количества операций?
Сколько приблизительно шагов потребуется бинарному поиску для массива из 1 000 000 элементов?
Что произойдёт с линейным поиском, если увеличить n в 100 раз?
Стоит ли сортировать массив ради единственного поиска? От чего зависит ответ?

Что показать преподавателю

Работающий код линейного и бинарного поиска.
Таблицу сравнений.
Демонстрацию ошибки применения бинарного поиска к неотсортированным данным.
Вывод о сложности O(n) и O(log n).

Ориентир по времени

10 минут — повторение; 40–45 минут — эксперименты и таблица; 20 минут — анализ; 5 минут — вывод. Резерв до 90 минут — дополнительное задание.

Дополнительное задание

Напишите функцию, которая выполняет 1000 поисков в одном и том же наборе данных. Сравните два подхода: 1000 линейных поисков и однократная сортировка + 1000 бинарных поисков. Сделайте вывод, когда стоимость предварительной сортировки начинает окупаться.