Курс 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
- Равенство и идентичность в Python
- Перевернуть список в Python
- Генерация фальшивых данных с Faker
- Основные методы NumPy
- Именованные срезы в Python
- Копирование файлов с shutil()
- Отладка утечек памяти в Python
- JMESPath в Python
- Скрытие вывода данных
- Решатель судоку на Python с pygame
- Поиск простых чисел
- Генераторы в Python
- Проверка версии Python
- Python groupby() из itertools: работа с повторяющимися элементами
- Модуль subprocess: запуск внешних команд
- Удаление символов новой строки в Python.
- Python UserString — создание подклассов строк
- Запуск внешних программ с subprocess
- Логирование в Python
- Оформление кода на Python
- Обработка StopIteration в Python
- Замена текста в Python
- Хэш-функции в Python
- Замена переменных в Python
- Фильтрация последовательности
- Разделение строки на пары ключ-значение.
- Создание словарей с defaultdict
- Оформление кода по PEP 8
- Работа с изображениями PIL
- Сравнение объектов в Python
- Метод __getitem__ в Python
- Метод join() для объединения элементов
- Defaultdict в Python
- Генератор чисел Фибоначчи
- Транспонирование матрицы в Python
- Возврат нескольких значений
- Получение текущей даты и времени с помощью datetime
- Оператор in для Python
- Разделение строки с помощью re.split()
- Преобразование данных в Python
- Преобразование Excel в PDF с Spire.XLS
- Использование type hints
- Форматирование заголовков в Python
- Дизассемблирование Python кода
- Глобальные переменные в Python
