Курс 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. Преобразование Excel в PDF с Spire.XLS
  2. F-строки в Python 3.8
  3. Установка Home Assistant
  4. Метод append() для списка
  5. Печать в одной строке
  6. Реверс строки в Python
  7. Упрощение работы с JSON-данными в Python
  8. TON Smart Challenge #2: участие и подготовка
  9. Группы исключений в Python
  10. Тестирование функции сложения
  11. Просмотр атрибутов и методов класса
  12. Улучшение читаемости кода в Python
  13. Python Ellipsis использование
  14. Работа с модулем glob в Python
  15. Строковое представление объектов
  16. Многоточие в Python
  17. Разделение строки на пары ключ-значение.
  18. Генератор чисел Фибоначчи
  19. Срезы в Python
  20. Библиотека sh: удобные команды терминала
  21. Перемещение и удаление файлов в Python
  22. Принцип одной функции
  23. Преобразование строк в числа с плавающей запятой
  24. Взаимодействие с внешними процессами в Python
  25. Метод rename() для переименования файлов и каталогов
  26. Управление памятью в Python
  27. Метод join для наборов
  28. Метод splitlines() для разделения строк
  29. Метод Self в Python
  30. Работа с процессами в Python
  31. Отладка регулярных выражений в Python
  32. Итераторы с потерямиZIP
  33. JSON в Python: модуль, dump, dumps, load
  34. Метод invert для побитового отрицания
  35. Библиотека schedule: планировщик задач
  36. Создание словарей и множеств в Python.
  37. Операции с кортежами
  38. Обновление данных через PUT запрос
  39. Бинарный поиск
  40. Преобразование строк в числа в Python
  41. Подписка на @SelectelNews
  42. Работа с дробями в Python
  43. Установка и использование TensorFlow
  44. Создание детектора плагиата
  45. Профилирование данных с Pandas
  46. Оператор += для объединения строк

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