Курс 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"
- Расчет времени выполнения программы
- Изучение объектов с помощью dir()
- Colorama: окрашивание текста в Python
- Метод hash в Python
- Разделение строки с регулярными выражениями
- Шаблоны Flask: условия и циклы
- Создание списка дат
- Избегайте двойного подчеркивания
- Проверка запуска скрипта или импорта модуля
- Подсказки типов в Python
- Декораторы в Python
- Библиотека funcy: удобные утилиты
- Поиск частых элементов в списке
- Атрибуты объекта в Python
- Перехват исключений в Python
- Работа с файлами в Python
- Работа с deque из collections
- Строковое представление объектов
- Обрезка изображения с Pillow
- Справка по импортированным модулям
- Моржовый оператор в Python 3.8
- GitHub в Telegram: подписка на уведомления
- Получение текущей даты в Python
- Генераторы в Python
- Передача параметров в Python
- Извлечение новостей с newspaper3k
- JMESPath в Python
- Разделение строки на подстроки в Python
- Наиболее частотные элементы с помощью Counter
- Объединение строк с помощью метода join
- Вызов внешних программ в Python с помощью sh
- Управление фоновыми задачами в Python
- Экспорт данных с помощью writefile
- Работа с комплексными числами в Python
- Введение в PyTorch
- Работа с библиотекой xkcd
- Псевдонимы в Python
- Лямбда-функции в Python
- Атрибуты класса и экземпляра в Python
- Работа с YAML в Python
- Управление контекстом выполнения кода
- Метод __iand__ для пользовательских классов
- Генерация тестовых данных с factory_boy
- Списки в Python: основы
- Присвоение и ссылки
- Названия переменных
