Курс 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
- Работа с модулем glob в Python
- Конкатенация строк в Python
- Метод lt для сортировки объектов
- Вызов функций по строке в Python.
- Python: цикл for и оператор присваивания
- Работа с файлами и директориями в Python.
- Удаление элементов из списка
- Сложные типы данных в Python
- Проверка на палиндром
- Импорт модулей и пакетов в Python
- Удаление дубликатов из списка
- Тестирование модели в PyTorch
- Переопределение метода __lshift__
- Работа с GitHub в Telegram
- Lambda Functions in Python
- Работа с массивами в Python
- Проверка ввода с помощью isdigit
- Работа с часовыми поясами в Python.
- Установка и использование emoji
- Деление в Python
- Работа со словарями с defaultdict из collections
- Python 3.12: Псевдонимы типов
- Инверсия списка и строки
- Игра «Виселица» на Python
- Генераторы в Python
- Лямбда-функции для min/max
- Запрос DELETE с библиотекой requests
- Оптимизация памяти с __slots__
- Красивый вывод списка
- Непрерывная проверка в Python
- Значения по умолчанию в Python
- Работа с файловой системой в Python
- Создание виртуальной среды
- Тайное преобразование типа ключа
- Проверка типов с использованием isinstance
- Изменение списка срезами
- Модуль pprint
- Определение объема памяти объекта
- Асинхронное программирование с asyncio
- Модуль functools в Python
- ROT13 Шифр Цезаря в Python
- Добавление цвета в консоли
- Отправка HTTP-запросов с User-Agent
