Курс 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"
- Хранение данных с помощью dataclasses
- Генераторы в Python
- Деление в Python
- Справка по импортированным модулям
- Форматирование объектов с модулем pprint
- Вакансии в Nebius
- Расчет времени выполнения
- Декораторы с аргументами в Python
- Установка и использование Logzero
- Класс UserDict: дополнительная функциональность
- Многострочные комментарии в Python
- Метод join() для объединения строк
- Хешируемые ключи в Python
- Объединение объектов в Python
- Генераторы данных
- Проверка памяти объекта
- Преобразование многоуровневого словаря
- Разделение строки с помощью split()
- Создание новых списков в Python
- Переменная с нижним подчеркиванием
- Объединение кортежей в Python
- Форматирование кода на Python
- Отображение графиков в Jupyter с Matplotlib
- Модуль pprint
- Получение текущего времени в Python
- Расчет времени выполнения кода
- PUT запрос для обновления данных
- Логирование с Loguru
- Многострочные комментарии в Python
- Работа с модулем bisect
- Генерация строк с .join()
- Проблема сравнения словарей
- Группировка элементов в словарь
- Копирование объектов в Python
- Метод округления чисел
- Изменение логики работы с временем
- Работа со словарями Python
- Методы работы со списками
- Функциональное программирование в Python
- Проверка условий в Python
- Управление экспортом элементов
- Константы в модуле cmath
- Magic Commands — улучшение работы с Python
- Функция print() — вывод информации
- Удаление первого элемента списка
- Метод ipow для возведения в степень
- Отступы в Python
- Оператор assert в Python















