Курс 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"
- Метод Enumerate() для списков
- Введение в Python
- Работа с областями видимости переменных
- Работа со словарями с defaultdict из collections
- Руководство по Pymorphy2
- Mad Libs Generator
- Управление доступом к модулю
- Создание обратного итератора
- Искажение имен в Python
- Форматирование строк в Python
- Управление фоновыми задачами в Python
- Установка и использование Telegram API в Python
- Хранение данных
- Сортировка с помощью параметра key
- Операции с кортежами
- Импорт классов из другого файла
- Значения по умолчанию в Python
- Работа с геоданными с помощью geopy
- Функции с дополнением
- Оператор zip в Python
- Упрощение условных выражений с тернарным оператором
- Изменение регистра данных
- Добавление элемента к кортежу
- Обновление множества в Python
- Оптимизация строк в Python
- Создание словарей с defaultdict()
- Функция enumerate в Python
- Регистрация на курсы SF Education
- Итерация по итерируемым объектам
- Группировка элементов Python
- Генератор списка с условием if
- Утечки переменных цикла в Python 3.x
- Метод join для наборов
- Вычисление логарифмов в Python
- Numpy: разбиение массивов
- Python enumerate() функции
- Работа с файловой системой в Python
- Условное добавление элементов в список
- Создание генераторов
- Форматирование строк с помощью f-строк
- Управление контекстом выполнения кода
- Скрытие вывода данных
- Метод invert для побитового отрицания
- Преобразование документов в PDF с помощью Spire.Office
- Функция sleep() в Python
- Класс Counter() для подсчета элементов
