Курс 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"
- Преобразование Excel в PDF с Spire.XLS
- F-строки в Python 3.8
- Установка Home Assistant
- Метод append() для списка
- Печать в одной строке
- Реверс строки в Python
- Упрощение работы с JSON-данными в Python
- TON Smart Challenge #2: участие и подготовка
- Группы исключений в Python
- Тестирование функции сложения
- Просмотр атрибутов и методов класса
- Улучшение читаемости кода в Python
- Python Ellipsis использование
- Работа с модулем glob в Python
- Строковое представление объектов
- Многоточие в Python
- Разделение строки на пары ключ-значение.
- Генератор чисел Фибоначчи
- Срезы в Python
- Библиотека sh: удобные команды терминала
- Перемещение и удаление файлов в Python
- Принцип одной функции
- Преобразование строк в числа с плавающей запятой
- Взаимодействие с внешними процессами в Python
- Метод rename() для переименования файлов и каталогов
- Управление памятью в Python
- Метод join для наборов
- Метод splitlines() для разделения строк
- Метод Self в Python
- Работа с процессами в Python
- Отладка регулярных выражений в Python
- Итераторы с потерямиZIP
- JSON в Python: модуль, dump, dumps, load
- Метод invert для побитового отрицания
- Библиотека schedule: планировщик задач
- Создание словарей и множеств в Python.
- Операции с кортежами
- Обновление данных через PUT запрос
- Бинарный поиск
- Преобразование строк в числа в Python
- Подписка на @SelectelNews
- Работа с дробями в Python
- Установка и использование TensorFlow
- Создание детектора плагиата
- Профилирование данных с Pandas
- Оператор += для объединения строк
