Полный Дзен Пайтона в одном канале
Разместить рекламу: @tproger_sales_bot
Правила общения: https://tprg.ru/rules
Другие каналы: @tproger_channels
Сайт: https://tprg.ru/site
Регистрация в перечне РКН: https://tprg.ru/xZOL
Post #3467
3.24K
Разбираемся в бинарном поиске на Python
Binary Search, или бинарный поиск — это эффективный способ найти элемент в отсортированном массиве. Принцип работы основан на делении массива пополам. Алгоритм постоянно уменьшает область поиска, пока не найдёт целевой элемент или не убедится, что его в массиве нет.
Вот как это происходит шаг за шагом. Сначала находим середину массива и сравниваем средний элемент с тем, который ищем. Если он совпадает с целевым, то задача выполнена. Если нет, и целевой элемент меньше среднего, ищем в левой половине массива. Если же больше — в правой. Процесс продолжается, пока не найдем элемент или массив не закончится.
Рассмотрим пример итеративного бинарного поиска на Python:
Аналогичный пример можно реализовать и рекурсивным методом:
Также можно использовать встроенную библиотеку
Важно помнить, что бинарный поиск работает только с отсортированными массивами. В этом его главный плюс и ограничение. Зато временная сложность у него составляет всего
#советы #алгоритмы
Binary Search, или бинарный поиск — это эффективный способ найти элемент в отсортированном массиве. Принцип работы основан на делении массива пополам. Алгоритм постоянно уменьшает область поиска, пока не найдёт целевой элемент или не убедится, что его в массиве нет.
Вот как это происходит шаг за шагом. Сначала находим середину массива и сравниваем средний элемент с тем, который ищем. Если он совпадает с целевым, то задача выполнена. Если нет, и целевой элемент меньше среднего, ищем в левой половине массива. Если же больше — в правой. Процесс продолжается, пока не найдем элемент или массив не закончится.
Рассмотрим пример итеративного бинарного поиска на Python:
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
elif guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Пример использования
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search(arr, target)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")
Аналогичный пример можно реализовать и рекурсивным методом:
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
elif guess > target:
return binary_search_recursive(arr, target, low, mid - 1)
else:
return binary_search_recursive(arr, target, mid + 1, high)
# Пример использования
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")
Также можно использовать встроенную библиотеку
bisect для выполнения бинарного поиска:import bisect
def binary_search_bisect(arr, x):
i = bisect.bisect_left(arr, x)
if i != len(arr) and arr[i] == x:
return i
else:
return -1
# Пример использования
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search_bisect(arr, x)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")
Важно помнить, что бинарный поиск работает только с отсортированными массивами. В этом его главный плюс и ограничение. Зато временная сложность у него составляет всего
O(log n), что значительно быстрее линейного поиска. Это делает бинарный поиск отличным выбором для работы с большими данными.#советы #алгоритмы
- 👍 11
- ❤🔥 1
