Курс 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 и Юникод: работа с цифрами
- Конкатенация строк с методом join()
- Методы работы со строками в Python
- Получение списка кортежей из словаря
- Сохранение Unicode в JSON
- Генерация QR-кодов с библиотекой qrcode
- Тестирование модели в PyTorch
- Оптимизация интернирования строк
- Освобождение памяти в Python
- Проверка элемента в множестве.
- Открытие, чтение и закрытие файла
- Библиотека Chartify: руководство
- Удаление символа из строки
- Создание задания в Cron
- Оператор «моржа» (Walrus Operator)
- Основные операции с Numpy
- Потоковый ввод в Python
- Чтение бинарного файла в Python.
- Повторение и перенос строки
- Разделение строки с помощью split()
- Управление памятью в Python
- Лямбда-функции в defaultdict
- Просмотр атрибутов и методов класса
- Python: отсутствие точек с запятыми
- Получение имени функции с помощью inspect
- Профилирование данных с Pandas
- Область видимости переменных в Python
- Модуль itertools: эффективная работа с итераторами
- Метод join() для объединения строк
- Поиск индекса элемента в списке
- Отношения подклассов в Python
- Декораторы в Python
- Управление виртуальными окружениями в Python
- Добавление элементов в список
- Работа с словарями в Python
- Класс UserDict: дополнительная функциональность
- Вывод с переменной через запятую
- Сортировка в Python
- Бесконечная проверка в Python
- Оптимизация параметров в Python
- None в Python: использование и особенности
- Обработка исключений в Python 3
- Транспонирование матрицы
- Работа с областями видимости переменных
