Курс 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. Преобразование range в итератор
  2. Оператор walrus в Python
  3. Измерение времени выполнения кода
  4. Копирование и вставка текста в Python
  5. Многоточие в Python
  6. Статическая типизация в Python
  7. Сортировка с параметром key
  8. Работа с географическими данными.
  9. Конкатенация списков в Python
  10. Создание списков в Python
  11. Капитализация строк
  12. Логирование в Python
  13. Удаление первого элемента списка
  14. Метод add для класса Vector
  15. Применение функции map() в Python
  16. Значения по умолчанию в Python
  17. Работа с GitHub в Telegram
  18. Основы работы с os
  19. Изменение логики работы с временем
  20. Удаление специальных символов
  21. Преобразование текста в речь с Python
  22. Метод Enumerate() для списков
  23. Основы слова
  24. Перевод двоичного кода в целое число
  25. Путь к интерпретатору Python
  26. Любовь к Python
  27. Нахождение самого длинного слова в списке с помощью max
  28. Создание функций высшего порядка
  29. Освоение Python
  30. Правила именования переменных
  31. Экранирование символов в Python
  32. Переименование файлов в Python
  33. Итераторы в Python
  34. Установка и использование pyshorteners
  35. Перезагрузка оператора в Python
  36. Создание коллекций из выражения-генератора
  37. Настройка шрифта и цвета в Tkinter
  38. Секреты Python
  39. Работа с аргументами командной строки
  40. Вывод с переменной через запятую
  41. Списковое включение в Python
  42. Область видимости переменных
  43. Метод clear для коллекций
  44. ChainMap избыточные ключи
  45. Оператор обр. импликации
  46. Импорт в Python: список all

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