Алгоритм бинарного поиска: полное руководство с кодом на Python
Реализация алгоритмов на Python: бинарный поиск
Задача поиска элемента в отсортированном массиве является классической. Бинарный поиск позволяет решить её за логарифмическое время. В этой статье рассматриваются различные способы реализации такого поиска на Python, их особенности и типичные ошибки.
Как реализовать бинарный поиск итеративно?
Итеративный подход является наиболее эффективным и предпочтительным. Он не использует дополнительную память и избегает риска переполнения стека.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Python типы данных задачи (задачи на типы данных в python)
Пояснение: Переменные left и right задают текущий интервал поиска. На каждом шаге вычисляется средний индекс mid. Если значение в этой позиции равно искомому, функция возвращает индекс. Если меньше, то поиск продолжается в правой половине, иначе - в левой. Условие while left <= right гарантирует, что интервал не пуст.
Типичные ошибки:
- Неправильное обновление границ: вместо
left = mid + 1иногда ошибочно пишутleft = mid, что может привести к бесконечному циклу. - Игнорирование случая, когда массив пуст - вызовет ошибку индекса.
- В языках с фиксированной длиной целых чисел
mid = (left + right) // 2может вызвать переполнение, но в Python это не проблема.
Случаи использования: Итеративный вариант подходит для большинства практических задач, где требуется быстрый поиск в неизменяемом отсортированном списке. Он легко читается и не зависит от глубины рекурсии.
Как реализовать бинарный поиск с помощью рекурсии?
Рекурсивная версия более лаконична, но уступает итеративной по производительности из-за накладных расходов на вызовы функций и ограничения глубины стека.
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
реализация алгоритмов на python (реализация алгоритмов)
Пояснение: Рекурсивная функция принимает границы интервала. Базовый случай - когда левая граница превышает правую, что означает отсутствие элемента. В противном случае вычисляется середина и выполняется рекурсивный вызов для соответствующей половины.
Возникающие проблемы:
- При большом размере массива глубина рекурсии может превысить лимит (обычно 1000). Решение - увеличить лимит через
sys.setrecursionlimitили использовать итеративный подход. - Необходимость передавать границы при каждом вызове - можно сделать внутреннюю вспомогательную функцию.
Случаи использования: Рекурсия удобна для демонстрации алгоритма в учебных целях и в ситуациях, когда естественным образом используется декомпозиция задачи.
Как использовать встроенный модуль bisect для бинарного поиска?
Модуль bisect предоставляет готовые функции для бинарного поиска в отсортированных списках. Это самый короткий и надёжный способ.
import bisect
def binary_search_bisect(arr, target):
i = bisect.bisect_left(arr, target)
if i != len(arr) and arr[i] == target:
return i
return -1
повторить цикл python (повторение цикла)
Пояснение: bisect_left возвращает позицию, на которую можно вставить элемент, сохраняя порядок. Если элемент присутствует, его индекс будет равен возвращённому. Проверка i != len(arr) необходима, чтобы избежать выхода за границы.
Типичные ошибки:
- Использование
bisectбез проверки равенства - может вернуть индекс, где элемента нет. - Забывание импортировать модуль.
- Попытка применить к неотсортированному списку - результат будет некорректен.
Случаи использования: Когда нужно вставить элемент в отсортированный список с сохранением порядка, или когда требуется быстрый, уже отлаженный бинарный поиск без написания собственного кода.
Как найти первое или последнее вхождение элемента?
Стандартный бинарный поиск возвращает произвольное вхождение, если дубликаты присутствуют. Для поиска границ используются модификации.
def find_first(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # ищем в левой части
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
Пояснение: При обнаружении элемента запоминаем его индекс, но продолжаем поиск в левой половине, чтобы найти первое вхождение. Аналогично для последнего вхождения - смещаем границу вправо.
Проблемы: Нужно чётко различать обновление границ для первого и последнего вхождения. Ошибка в условии может привести к бесконечному циклу.
Случаи использования: При работе с большими наборами данных, содержащими дубликаты (например, словарь с повторяющимися ключами).
Расширенные примеры реализации бинарного поиска
Поиск в циклически сдвинутом отсортированном массиве
Дан массив, который был отсортирован, а затем сдвинут (например, [4,5,6,1,2,3]). Требуется найти элемент за O(log n).
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[left] <= arr[mid]: # левая половина отсортирована
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else: # правая половина отсортирована
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
# Пример arr = [4,5,6,1,2,3] print(search_rotated(arr, 5)) # 1 print(search_rotated(arr, 3)) # 5 print(search_rotated(arr, 7)) # -1
Пояснение: Алгоритм определяет, какая половина массива отсортирована, и решает, в какой половине может находиться искомое значение. Сложность - O(log n).
Поиск элемента в массиве неизвестного размера (бесконечный массив)
Если размер массива неизвестен, но он отсортирован, можно сначала экспоненциально расширять границы.
def binary_search_infinite(arr, target):
# Приблизительная верхняя граница
if arr[0] == target:
return 0
left, right = 0, 1
while right < len(arr) and arr[right] < target:
left = right
right *= 2
# Теперь обычный бинарный поиск между left и min(right, len(arr)-1)
high = min(right, len(arr)-1)
while left <= high:
mid = (left + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
high = mid - 1
return -1
# Пример (реальный массив конечен, но имитируем бесконечный) arr = list(range(1000)) print(binary_search_infinite(arr, 345)) # 345 print(binary_search_infinite(arr, 1001)) # -1
Пояснение: Экспоненциальный рост границы позволяет быстро локализовать область поиска. Применяется в потоковых данных или при работе с большими объёмами.
Бинарный поиск с интерполяцией (Interpolation Search)
Для равномерно распределённых данных можно использовать интерполяцию для более точной оценки позиции.
def interpolation_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right and target >= arr[left] and target <= arr[right]:
if left == right:
return left if arr[left] == target else -1
# пропорциональная оценка
pos = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])
if arr[pos] == target:
return pos
if arr[pos] < target:
left = pos + 1
else:
right = pos - 1
return -1
# Пример arr = [10, 20, 30, 40, 50] print(interpolation_search(arr, 30)) # 2 print(interpolation_search(arr, 5)) # -1
Пояснение: В лучшем случае сложность O(log log n), но в худшем (неравномерное распределение) может деградировать до O(n). Подходит для больших, равномерно распределённых массивов.
Использование bisect для вставки с сохранением порядка
Модуль bisect позволяет не только искать, но и вставлять элементы в отсортированный список.
import bisect
arr = [1, 3, 5, 7]
bisect.insort_left(arr, 4)
print(arr) # [1, 3, 4, 5, 7]
bisect.insort_right(arr, 5)
print(arr) # [1, 3, 4, 5, 5, 7]
# Результат [1, 3, 4, 5, 7] [1, 3, 4, 5, 5, 7]
Пояснение: insort_left вставляет элемент перед существующими равными, insort_right - после. Эти функции предпочтительнее ручного поиска и вставки, так как работают за O(log n + n) из-за вставки.
Бинарный поиск в двумерном отсортированном массиве
Если матрица отсортирована по строкам и столбцам, можно найти элемент за O(m + n).
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
row += 1
else:
col -= 1
return False
# Пример
matrix = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 10)) # False
Пояснение: Начинаем с правого верхнего угла. Если текущее значение меньше цели, спускаемся вниз; если больше - идём влево. Это не бинарный поиск в чистом виде, но использует идею сужения пространства.
Поиск пика в массиве (peak finding) с помощью бинарного подхода
Задача: найти любой пик (элемент, который больше своих соседей) в массиве, не обязательно отсортированном.
def find_peak(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > arr[mid + 1]:
right = mid
else:
left = mid + 1
return left
# Пример arr = [1, 2, 3, 1] print(find_peak(arr)) # 2 (значение 3) arr = [1, 2, 1, 3, 5, 6, 4] print(find_peak(arr)) # 5 (значение 6) или 2 (значение 2) - зависит от направления сравнения
Пояснение: Алгоритм работает за O(log n). Сравнение с соседом определяет, в какой половине гарантированно есть пик.