Курс 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"
- Создание треугольника Паскаля
- Многопоточность в Python
- Counter() — подсчет элементов
- Python enumerate() использование
- Удаление ссылок в Python
- Объединение итераторов
- Форматирование даты с strftime()
- Метод get для словарей
- Переворот списка в Python
- Генераторы в Python
- Сложение матриц в NumPy
- Переопределение метода __rshift__
- Сохранение Unicode в JSON
- Форматирование строк в Python
- inspect в Python: анализ кода
- Пространство имен в Python
- Кортеж в Python: создание и использование
- Декораторы для регистрации функций
- Оператор += в Python
- Python: отсутствие точек с запятыми
- Перегрузка операторов в Python
- Методы Python для работы с данными
- Функция zip() для объединения списков
- Присоединение элементов коллекции
- Python groupby() из itertools: работа с повторяющимися элементами
- Функции-генераторы в Python
- Создание и операции с дробями
- Сортировка данных с лямбда-функциями
- Использование defaultdict в Python
- Поиск частого элемента
- Оператор @ для умножения матриц
- Транспонирование матрицы
- Импорт модуля из другого каталога
- Проверка на истинность объектов в Python
- Модуль itertools: эффективная работа с итераторами
- Аргумент по умолчанию
- ChainMap.new_child() — добавление нового словаря
- Извлечение аудио из видео
- Переопределение метода xor в Python
- Управление импортом в Python
- Работа с контекстными переменными
- Присвоение значений переменным в Python
- Генерация резюме в Gensim
- Lambda-функция в Python: использование с map() и sum()
- Проблема с изменяемыми аргументами
- Ускоренный импорт библиотек
- Форматирование строк в Python
