Курс 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. Хранение данных с помощью dataclasses
  2. Генераторы в Python
  3. Деление в Python
  4. Справка по импортированным модулям
  5. Форматирование объектов с модулем pprint
  6. Вакансии в Nebius
  7. Расчет времени выполнения
  8. Декораторы с аргументами в Python
  9. Установка и использование Logzero
  10. Класс UserDict: дополнительная функциональность
  11. Многострочные комментарии в Python
  12. Метод join() для объединения строк
  13. Хешируемые ключи в Python
  14. Объединение объектов в Python
  15. Генераторы данных
  16. Проверка памяти объекта
  17. Преобразование многоуровневого словаря
  18. Разделение строки с помощью split()
  19. Создание новых списков в Python
  20. Переменная с нижним подчеркиванием
  21. Объединение кортежей в Python
  22. Форматирование кода на Python
  23. Отображение графиков в Jupyter с Matplotlib
  24. Модуль pprint
  25. Получение текущего времени в Python
  26. Расчет времени выполнения кода
  27. PUT запрос для обновления данных
  28. Логирование с Loguru
  29. Многострочные комментарии в Python
  30. Работа с модулем bisect
  31. Генерация строк с .join()
  32. Проблема сравнения словарей
  33. Группировка элементов в словарь
  34. Копирование объектов в Python
  35. Метод округления чисел
  36. Изменение логики работы с временем
  37. Работа со словарями Python
  38. Методы работы со списками
  39. Функциональное программирование в Python
  40. Проверка условий в Python
  41. Управление экспортом элементов
  42. Константы в модуле cmath
  43. Magic Commands — улучшение работы с Python
  44. Функция print() — вывод информации
  45. Удаление первого элемента списка
  46. Метод ipow для возведения в степень
  47. Отступы в Python
  48. Оператор assert в Python

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