Курс 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 с PrettyTable
- Переворот последовательности
- Установка переменной среды в Python
- Зарезервированные слова в Python
- Сглаживание списка
- Генератор данных в Keras
- Создание объекта timedelta
- Управление браузером с Selenium
- Множества и frozenset
- Импорт модулей в Python 3.12
- Удаление элементов из списка
- Метод enumerate() в Python
- Управление мышью и клавиатурой с Pyautogui
- Метод index() в Python
- Работа с Requests для HTTP-запросов
- Подсчет вхождений элементов
- Логирование с Logzero
- Конкатенация строк в Python
- Анонимные функции в Python
- Методы сравнения множеств
- Извлечение чисел из текста
- Оператор Walrus в Python
- Измерение времени выполнения кода
- Печать календаря
- Python Аргументы по умолчанию
- Создание копии списка в Python
- Оптимизация памяти с slots
- Философия Python
- Логирование с Loguru
- Получение значений из словарей
- kwargs в Python
- Нахождение разницы между списками в Python
- Работа с файловой системой в Python
- Проверка переменных окружения в Python
- Установка и использование модуля «howdoi»
- Форматирование строк в Python.
- Оптимизация памяти с __slots__
- Отправка HTTP-запросов с User-Agent
- Равенство и идентичность в Python
- Установка и использование Virtualenv
- Функция с **kwargs в Python
- Разделение строки на подстроки в Python
- Python 3.12: Псевдонимы типов
- Изучение объектов с помощью dir()
- Выбор редактора кода.
- Поиск с помощью регулярных выражений
