Курс 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"
- Измерение времени выполнения кода с помощью time
- Профилирование кода на Python
- Удаление дубликатов из списка с помощью dict.fromkeys
- Получение атрибутов и методов класса
- Копирование списков в Python
- Генерация UUID в Python
- Метод pos в Python
- Работа с географическими данными.
- Игра «Виселица» на Python
- Блок else в циклах.
- Экспорт данных с помощью writefile
- Pillow: работа с изображениями
- Применение функции к списку
- Разделение функций на этапы
- Преобразование строк в числа в Python
- Форматирование объектов с модулем pprint
- Операция += для списков
- Скачать видео с YouTube
- Работа с множествами в Python
- Декораторы в Python
- Запрос пароля с помощью getpass
- Обработка исключений
- Глобальные переменные в Python
- Модуль array: создание и использование массивов
- Генераторные функции в Python
- Работа с комбинациями в Python.
- Класс-оболочка для словарей
- Упрощенный вывод данных в Python
- Перевод двоичного кода в целое число
- Оператор del в Python
- Генерация случайных чисел Python
- Создание новых списков в Python
- Хешируемые ключи в Python
- Создание namedtuple списком полей
- Непрерывная проверка в Python
- Форматирование вывода списков
- Печать календаря в Python
- Оператор continue в Python
- Искажение имен в Python
- Сериализация данных в JSON с помощью json.dumps
- List Comprehension Tutorial
- Тип CodeType в Python.
- Динамическая типизация в Python
- Combobox в Tkinter
- Доступ к локальным переменным
