Курс 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"

  1. JSON в Python: модуль, dump, dumps, load
  2. Установка и загрузка Instaloader
  3. Переопределение метода __eq__
  4. Множества и frozenset
  5. Решение переменной Шредингера
  6. Инициализация структур данных
  7. Библиотека schedule: планировщик задач
  8. Округление банкира в Python
  9. Библиотека Chartify: руководство
  10. Тестирование с responses
  11. Работа с контекстным менеджером Pool
  12. Анонимные функции в Python
  13. Списки в Python
  14. Работа с датой и временем в Python
  15. Numpy: разбиение массивов
  16. Порядок и длина множеств в Python
  17. Обработка исключений в Python
  18. Возвращение нескольких значений
  19. Работа с Path в Python
  20. Экспорт данных в файл.
  21. Аннотации типов в Python
  22. Декораторы в Python
  23. Извлечение новостей с newspaper3k
  24. Инверсия списка/строки в Python
  25. Работа с необработанными строками
  26. Вакансии в Nebius
  27. Принципы SRP и OCP
  28. Встроенные функции Python
  29. Группы исключений в Python
  30. Управление IP-адресами через прокси
  31. Игра «Камень, ножницы, бумага» — Python
  32. CLI-инструмент howdoi
  33. Создание уникального проекта
  34. Поиск самого частого элемента
  35. Оператор del в Python
  36. Запрос DELETE с библиотекой requests
  37. Проверка версии Python
  38. Автоматизация скриптов на AWS Lightsail.
  39. Модуль pprint
  40. Объединение списков в Python
  41. Передача словаря через **kwargs
  42. Хэш-функции и метод цепочек
  43. SciPy: широкий функционал для математических операций
  44. Делегирование в Python

Marketello читают маркетологи из крутых компаний