lab04 — поиск: линейный и бинарный¶
Массив из 10 случайных чисел и два способа поиска в нём: простым перебором (линейный) и бинарный (по отсортированному массиву). Отдельно — формирование отсортированной последовательности из вводимых с клавиатуры чисел через сортировку вставками, чтобы по ней работал бинарный поиск.
Массив и print_array совпадают с предыдущими лабораторными: заполнение через random.randint(1, 100), печать по индексам через собственную array_length (без встроенных len/range). Сортировка вставками переиспользуется из lab03 — from labs.lab03 import insertion_sort.
Поиск простым перебором¶
Перебор проходит массив слева направо и сравнивает каждый элемент с искомым. Четыре функции отличаются только тем, что они возвращают.
def linear_contains(arr: list[int], target: int) -> bool:
i = 0
while i < array_length(arr):
if arr[i] == target:
return True
i += 1
return False
| Функция | Возвращает | Когда не найдено |
|---|---|---|
linear_contains |
True / False |
False |
linear_first_index |
индекс первого вхождения | -1 |
linear_all_indices |
список индексов всех вхождений | -1 |
linear_count |
количество вхождений | 0 |
linear_contains и linear_first_index завершаются на первом же совпадении (досрочный return), поэтому в среднем проходят полмассива. linear_all_indices и linear_count обязаны дойти до конца — им нужно учесть все вхождения. Сложность всех четырёх — O(n), дополнительной памяти не требуется (кроме списка индексов у linear_all_indices).
def linear_all_indices(arr: list[int], target: int) -> list[int] | int:
indices: list[int] = []
i = 0
while i < array_length(arr):
if arr[i] == target:
indices.append(i)
i += 1
if not indices:
return -1
return indices
По условию задания «индексы всех вхождений / −1»: при отсутствии элемента возвращается не пустой список, а -1.
Бинарный поиск¶
Идея: в отсортированном массиве можно на каждом шаге сравнить искомое значение с серединой диапазона и отбросить ту половину, где элемента заведомо нет. Так зона поиска уменьшается вдвое за шаг.
def binary_search(arr: list[int], target: int) -> int:
low = 0
high = array_length(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
low = mid + 1 # искомое правее середины
else:
high = mid - 1 # искомое левее середины
return -1
Условие цикла low <= high (а не <) важно: иначе одиночный оставшийся элемент не будет проверен. Сложность — O(log n): на каждой итерации диапазон уменьшается вдвое.
Главное ограничение: бинарный поиск работает только на отсортированном массиве. На неотсортированных данных он может не найти присутствующий элемент.
binary_search_sorted объединяет задание 3 целиком: сначала сортирует массив вставками (insertion_sort из lab03), затем ищет в результате. Входной массив не мутируется — сортировка возвращает новый список.
def binary_search_sorted(arr: list[int], target: int) -> tuple[int, list[int]]:
sorted_arr, _ = insertion_sort(arr)
return binary_search(sorted_arr, target), sorted_arr
Формирование отсортированной последовательности вводом¶
Задание 4: вводимые с клавиатуры числа сразу формируют отсортированную последовательность. Каждое новое число вставляется в нужное место уже отсортированной части — это один шаг сортировки вставками.
def insert_sorted(sorted_arr: list[int], value: int) -> list[int]:
result = list(sorted_arr)
result.append(value)
j = array_length(result) - 2
while j >= 0 and result[j] > value:
result[j + 1] = result[j] # сдвигаем больши́й элемент вправо
result[j] = value
j -= 1
return result
build_sorted_sequence строит последовательность из готового списка значений (удобно для тестов), а read_sorted_sequence делает то же самое, читая числа через input() и показывая после каждого ввода текущее состояние:
def build_sorted_sequence(values: list[int]) -> list[int]:
result: list[int] = []
i = 0
while i < array_length(values):
result = insert_sorted(result, values[i])
i += 1
return result
Поскольку каждый элемент вставляется за O(n), построение всей последовательности из n чисел — O(n²), как и обычная сортировка вставками.
Бинарный поиск во введённой последовательности¶
Задание 5 — это применение того же binary_search к последовательности, полученной в задании 4. Так как она уже отсортирована вставками при вводе, дополнительной сортировки не требуется: бинарный поиск применим напрямую.
Меню¶
menu генерирует массив и в цикле читает выбор пользователя:
| Пункт | Действие |
|---|---|
| 1 | Поиск перебором: все четыре варианта результата сразу |
| 2 | Бинарный поиск с предварительной сортировкой вставками |
| 3 | Ввести 10 чисел с клавиатуры → отсортированная последовательность |
| 4 | Бинарный поиск в текущем (отсортированном) массиве |
| 5 | Сгенерировать новый массив |
| 0 | Выход |
Пункт 3 заменяет текущий массив введённой отсортированной последовательностью, после чего пункт 4 (бинарный поиск) корректно по ней работает.
Где это в проде¶
Линейный поиск — это «прогрепать как есть», бинарный — «сначала отсортируй/проиндексируй, потом ищи дёшево»:
- Бинарный поиск под капотом стандартных инструментов.
bisectв Python,sort.Search/slices.BinarySearchв Go, поиск по индексу БД (B-tree — это обобщение бинарного поиска на дерево), поиск ключа в отсортированных SSTable у LSM-движков (Cassandra, RocksDB, ClickHouse).git bisect— буквально бинарный поиск по истории коммитов в поисках того, что сломало сборку. - Главный размен — индекс. Бинарный поиск требует отсортированных данных, а сортировка стоит O(n log n). Поэтому его применяют, когда искать будут многократно: платим за сортировку/построение индекса один раз, дальше каждый поиск — O(log n) вместо O(n). Это ровно причина, по которой БД строят индексы заранее, а не сканируют таблицу на каждый запрос (index scan против seq scan в плане).
Параллельная реализация на Go¶
Линейный и бинарный поиск реализованы на Go в пакете src/golang/dsa/lab04. Как и в Python, BinarySearchSorted сортирует копию входа сортировкой вставками из пакета lab03 и затем ищет. Ниже — сам бинарный поиск.