Курс 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"
- Преобразование range в итератор
- Оператор walrus в Python
- Измерение времени выполнения кода
- Копирование и вставка текста в Python
- Многоточие в Python
- Статическая типизация в Python
- Сортировка с параметром key
- Работа с географическими данными.
- Конкатенация списков в Python
- Создание списков в Python
- Капитализация строк
- Логирование в Python
- Удаление первого элемента списка
- Метод add для класса Vector
- Применение функции map() в Python
- Значения по умолчанию в Python
- Работа с GitHub в Telegram
- Основы работы с os
- Изменение логики работы с временем
- Удаление специальных символов
- Преобразование текста в речь с Python
- Метод Enumerate() для списков
- Основы слова
- Перевод двоичного кода в целое число
- Путь к интерпретатору Python
- Любовь к Python
- Нахождение самого длинного слова в списке с помощью max
- Создание функций высшего порядка
- Освоение Python
- Правила именования переменных
- Экранирование символов в Python
- Переименование файлов в Python
- Итераторы в Python
- Установка и использование pyshorteners
- Перезагрузка оператора в Python
- Создание коллекций из выражения-генератора
- Настройка шрифта и цвета в Tkinter
- Секреты Python
- Работа с аргументами командной строки
- Вывод с переменной через запятую
- Списковое включение в Python
- Область видимости переменных
- Метод clear для коллекций
- ChainMap избыточные ключи
- Оператор обр. импликации
- Импорт в Python: список all
