Курс 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. Оптимизация интернирования строк
  2. Исключение NotImplementedError
  3. Функции map, filter и reduce
  4. Работа с часовыми поясами в Python
  5. Форматирование строк в Python.
  6. Измерение времени выполнения кода
  7. Получение имени функции с помощью inspect
  8. Работа с географическими данными.
  9. Принципы SRP и OCP
  10. Цикл for в Python
  11. Отладка регулярных выражений в Python
  12. Defaultdict в Python
  13. Создание новых списков в Python
  14. Разработка Telegram-ботов
  15. Глобальные переменные в Python
  16. Непрерывная проверка в Python
  17. Вызов внешних программ в Python с помощью sh
  18. Преобразование range в итератор
  19. Модуль functools в Python
  20. Функции в Python
  21. Область видимости переменных
  22. Срез списка в Python
  23. UserString в Python
  24. Основные операции с Numpy
  25. Глобальные переменные в Python
  26. Декораторы в Python
  27. Замена подстроки
  28. Реализация метода __abs__ в Python
  29. Метод pos в Python
  30. Проверка файла .py на синтаксис.
  31. Python Calendar Usage
  32. Замена текста с помощью sub
  33. Векторизация в Python с NumPy.
  34. Генерация резюме в Gensim
  35. Капитализация строк
  36. Копирование и вставка текста в Python
  37. Метод ipow для возведения в степень
  38. Создание итератора
  39. Создание таблиц в терминале с PrettyTable
  40. Оператор is в Python
  41. Переопределение унарных операторов
  42. Цепные операции в Python
  43. Автоматизация скриптов на AWS Lightsail.
  44. Метод gt в Python
  45. Аргументы *args и **kwargs

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

Добавить
свою компанию