Курс 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"
- JSON в Python: модуль, dump, dumps, load
- Установка и загрузка Instaloader
- Переопределение метода __eq__
- Множества и frozenset
- Решение переменной Шредингера
- Инициализация структур данных
- Библиотека schedule: планировщик задач
- Округление банкира в Python
- Библиотека Chartify: руководство
- Тестирование с responses
- Работа с контекстным менеджером Pool
- Анонимные функции в Python
- Списки в Python
- Работа с датой и временем в Python
- Numpy: разбиение массивов
- Порядок и длина множеств в Python
- Обработка исключений в Python
- Возвращение нескольких значений
- Работа с Path в Python
- Экспорт данных в файл.
- Аннотации типов в Python
- Декораторы в Python
- Извлечение новостей с newspaper3k
- Инверсия списка/строки в Python
- Работа с необработанными строками
- Вакансии в Nebius
- Принципы SRP и OCP
- Встроенные функции Python
- Группы исключений в Python
- Управление IP-адресами через прокси
- Игра «Камень, ножницы, бумага» — Python
- CLI-инструмент howdoi
- Создание уникального проекта
- Поиск самого частого элемента
- Оператор del в Python
- Запрос DELETE с библиотекой requests
- Проверка версии Python
- Автоматизация скриптов на AWS Lightsail.
- Модуль pprint
- Объединение списков в Python
- Передача словаря через **kwargs
- Хэш-функции и метод цепочек
- SciPy: широкий функционал для математических операций
- Делегирование в Python















