Курс 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"
- Создание генераторов
- Метод pop() списка
- Функция sleep() в Python
- Beautiful Soup — извлечение данных из HTML
- Настройка логгера Logzero
- Генераторные выражения и islice.
- Реверс строки и списка в Python.
- Получение ID текущего процесса
- Проверка запуска скрипта или импорта модуля
- Передача словаря через **kwargs
- Функция eval() в Python
- Быстрый поиск кода
- Копирование списков в Python
- Строковое представление объектов
- Печать месячного календаря
- Именованные срезы в Python
- Работа с timedelta
- Цикл for с enumerate() в Python
- Создание класса в Python
- Обработка ошибок ввода данных
- Проверка элемента в множестве.
- Принципы Zen Python
- JMESPath в Python
- Генератор чисел Фибоначчи
- Удаление дубликатов из списка с помощью dict.fromkeys
- Анонимные функции Lambda
- Методы обработки строк в Python
- Официальный канал Python в Telegram
- Сравнение def и lambda функций в Python
- Работа с функцией next() в Python
- Оператор объединения словарей
- Подсчет элементов в списке с Counter
- Логирование в Python
- Оператор zip в Python
- Генераторы в Python
- Установка и использование Python-dateutil
- Просмотр файла в Jupyter Noteboo
- Установка и использование модуля Wikipedia
- Метод title() в Python
- Работа с очередями в Python
- Форматирование данных с помощью pprint
- Методы __repr__ и __str__ в Python
- Метод pos в Python
- Основные операции с библиотекой Numpy
- Философия Python
- Обновление данных через PUT запрос
- Установка и использование Virtualenv
