Курс 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"
- Python Тесты и Гайды
- Работа с изображениями Pillow
- Работа с временем в Python
- Работа с deque из collections
- Выход из профиля в Django
- Реализация операции -= для пользовательского класса
- Транспонирование 2D-массива с помощью zip
- Резервирование символов в Python
- Добавление вложенных списков
- Функциональное программирование.
- Создание вкладок с TKinter
- Списковый компрехеншен.
- Сортировка данных с лямбда-функциями
- Оптимизация памяти с __slots__
- Python groupby() из itertools: работа с повторяющимися элементами
- Создание новой даты в Python
- globals и locals
- Игра «Угадывание чисел»
- Расчет времени выполнения
- Именованные срезы в Python
- Условные выражения в Python
- Расширение информации об ошибке в Python
- Таймер обратного отсчета
- Метод __ilshift__ для битового сдвига влево
- Работа с типами данных в Python с помощью pydantic.
- Преобразование символов в нижний регистр
- Создание множества в Python
- Однострочники Python
- Управление контекстом выполнения
- Отправка HTTP-запросов в Python
- Python itertools combinations() — группировка элементов
- Пустой оператор pass в Python
- Декораторы с @wraps
- Удаление элементов из списка в Python
- Поиск самого частого элемента
- Вычисление фазы комплексного числа
- Метод lt для сортировки объектов
- Деление в Python
- Наследование в программировании
- Многострочные строки в Python
- Вычисление натурального логарифма в NumPy
- Атрибуты класса и экземпляра
- Сравнение def и lambda-функций
- Экспорт внешнего файла с помощью writefile
