Курс 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"
- Инициализация структур данных
- Установка и обучение ChatterBot
- Замеры производительности в Python
- Метод rxor для операции побитового исключающего «или»
- Библиотека Emoji: использование смайлов в Python
- Очистка списка от False, None, 0, «»
- Скрытие вывода данных
- Заказ карты Тинькофф Black
- Pretty-printing JSON в Python
- Конвертация изображений в PDF
- Обмен данными с asyncio.Queue
- Создание комплексных чисел
- Оператор break в Python
- Создание функций высшего порядка
- Работа с файловой системой в Python
- Объединение словарей в Python
- Метод __irshift__ для побитового сдвига вправо
- Условные выражения в Python
- Lambda-функция в Python: использование с map() и sum()
- Работа с процессами в Python
- Удаление дубликатов с помощью множеств
- Протокол управления контекстом
- Модуль os: работа с файлами и папками
- Подсчет частотности элементов в Python
- Поиск самого частого элемента
- Работа с областями видимости переменных
- Python itertools combinations() — группировка элементов
- Наиболее частотные элементы с помощью Counter
- Ускорение кода с помощью векторизации
- Итерация по итерируемым объектам
- Разделение строки в Python
- Удаление элементов из списка в Python.
- Поиск индекса элемента
- Функция enumerate в Python
- Python groupby() из itertools: работа с повторяющимися элементами
- Многопроцессорное программирование в Python
- Расчет времени выполнения программы
- Конкатенация строк с помощью join()
- Форматирование строк в Python
- Циклы for в Python
- Необязательные аргументы в Python
- Установка Git и AWS CLI
- Роль ключевого слова self
- Python 3.12: переиспользование кавычек
- Курс Data Scientist в медицине
- Возврат значений из генератора
- Хеширование паролей с использованием salt
