Двоичный поиск в Python
Двоичный поиск после каждого сравнения уменьшает область вдвое.
Что такое Двоичный поиск в Python?
Двоичный поиск после каждого сравнения уменьшает область вдвое.
Быстро найдите значение в отсортированном списке.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Визуализация: Двоичный поиск в Python
O(log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
main.py
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))Ожидаемый результат
3Как это работает
Средний элемент определяет нужную половину. Время O(log n), вход должен быть отсортирован.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.