Курс 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 3.12
- Логирование с Logzero
- Работа со случайными элементами
- Комментарии в Python
- Удаление символа из строки
- Создание графиков в терминале
- Лямбда-функции в defaultdict
- Поиск наиболее частого элемента
- Деление в Python
- Лямбда-функции в Python
- Проблема сравнения словарей
- Возврат нескольких значений
- Конструктор в Python
- Метод difference_update() — разность множеств
- Многопоточность в Python
- Замена символов в строке
- Рациональные числа в Python
- Сортировка HTML-элементов
- Метод bool() в Python
- PrettyTable: создание таблицы
- Обработка исключений в Python
- Метод join() для объединения элементов строки
- Методы HTTP запросов в Flask
- Списки в Python: синтаксис представления
- Создание директории в Python
- Создание файла с проверкой ошибки
- Управление виртуальными средами в Python
- Метод join для наборов
- Преобразование кортежа в словарь.
- Работа с утверждениями в Python
- Метод append() для списка
- Измерение времени выполнения
- Переопределение метода __and__
- Декодирование строк в Python
- Проверка подстроки в строке
- Подсказки при вводе данных в Python
- Создание вложенных циклов for
- Определение объема памяти объекта
- Бинарный поиск
- Обмен переменными в Jupyter
- Форматирование объектов с модулем pprint
- Оператор in для проверки наличия элемента
- Форматирование строк в Python
- Работа с collections в Python.
- Проверка на палиндром
- Функции map, filter, reduce
