Курс 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
- Combobox в Tkinter
- Освобождение памяти в Python
- Объединение словарей в Python
- Отправка POST запроса на сервер.
- Фильтрация данных в Python.
- Вложенные генераторы в Python
- Установка максимального количества цифр
- Нахождение пересечения множеств
- Работа с каталогами в Python
- F-строки в Python 3.8
- Работа с timedelta
- Декораторы в Python
- Работа с PosixPath() в Python
- Переменная с нижним подчеркиванием
- Разработка игры Pong с turtle
- Область видимости переменных
- Создание .exe файла с pyinstaller
- Поиск индексов подстроки
- Структурирование данных с Pydantic
- Лямбда-функции в Python
- Отступы в Python
- Сортировка с помощью параметра key
- Метод join() для объединения элементов
- Логические значения в Python
- Рекурсия для обращения строки
- Функция all() в Python
- Модуль functools в Python
- Обновление данных через PUT запрос
- Создание графики с черепахой
- Декораторы с @wraps
- Резервирование символов в Python
- Подсчет количества элементов в списке
- Просмотр внешних файлов в %pycat
- Функция rsplit() в Python
- Списковое включение в Python
- Перетасовка списков в Python
- Лямбда-функции в цикле
- Преобразование символов в нижний регистр
- Обработка исключений в Python
- Активация Matplotlib в Jupyter
- Генераторы по генератору
- Многострочные строки в Python
- Работа с кортежами в Python
- Отладка производительности Python
- Метод radd для пользовательских чисел
- Нахождение хеша для бесконечности и NaN в Python
