Курс Python → Бинарный поиск
Алгоритм бинарного поиска — это эффективный метод поиска элемента в отсортированном массиве. Он основан на принципе «разделяй и властвуй», который позволяет быстро сузить область поиска. Для начала работы алгоритм принимает отсортированный список, в котором будет осуществляться поиск. Затем алгоритм постоянно сравнивает значение поиска с серединой массива.
В зависимости от результата сравнения, алгоритм либо сужает область поиска до левой или правой половины массива, либо находит искомый элемент. Этот процесс продолжается до тех пор, пока не будет найден искомый элемент или область поиска сузится до пустого массива. Благодаря этому непрерывному делению массива на две части, алгоритм обеспечивает логарифмическую временную сложность.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Пример кода выше представляет функцию бинарного поиска на Python. Она принимает отсортированный массив и значение, которое необходимо найти в этом массиве. Функция последовательно сравнивает значение поиска с серединой массива и сужает область поиска до тех пор, пока не будет найден искомый элемент или область поиска не станет пустой. Если элемент найден, функция возвращает его индекс в массиве, в противном случае возвращается -1.
Другие уроки курса "Python"
- Работа с IP-адресами в Python
- Построение графиков в Matplotlib
- Docstring в Python
- Функция enumerate() в Python
- Метод ifloordiv для пользовательских классов
- Оператор морж в Python 3.8
- Простой калькулятор Python
- HTTP-запросы с библиотекой Requests
- Списки в Python: основы
- Сравнение def и lambda функций в Python
- Срезы в Python
- Отладка в командной строке
- Проверка класса объекта
- Работа с Path в Python
- Создание словарей с defaultdict()
- Добавление элемента к кортежу
- Отслеживание выполнения программы с библиотекой tqdm
- Преобразование типов данных в set comprehension
- Управление памятью в Python
- Метод rmatmul для обратного матричного умножения
- Генераторные выражения и islice.
- Замена символов в Python
- Работа с итераторами в Python
- Создание новых списков через list comprehensions
- Хранение данных с помощью dataclasses
- Генераторы списков в Python
- Работа с zip()
- Преобразование генераторов в циклы
- Метод сравнения объектов в Python
- Работа с асинхронными задачами в Python
- Работа с типами данных в Python с помощью pydantic.
- Выражения-генераторы в Python
- Python reversed() функция
- Запуск асинхронной корутины
- Многострочные комментарии в Python
- Присвоение значений переменным в Python
- Просмотр атрибутов и методов класса
- Numpy: разбиение массивов
- Цикл for с enumerate() в Python
- Область видимости переменных
- Метод gt в Python
- Декораторы в Python
- Основы Python за 14 дней
- Функция __init__ в Python
