Курс 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. Нахождение самого длинного слова в списке с помощью max
  2. Структура данных deque в Python
  3. Преобразование данных в Python
  4. Python reversed() vs срез[::-1]
  5. Форматирование строк в Python
  6. Создание даты из строки ISO
  7. Модуль math: основные функции
  8. Удаление элемента по индексу в Python
  9. Обязательные аргументы в Python
  10. Списковое включение в Python
  11. Подсчет элементов в Python
  12. Создание комплексных чисел
  13. Списковое включение в Python
  14. Работа с zip-архивами в Python
  15. Конкатенация строк с методом join()
  16. Изменение объектов в Python
  17. Сортировка элементов с OrderedDict
  18. Конвертация изображений в PDF
  19. Управление экспортом элементов
  20. Python: цикл for и оператор присваивания
  21. Искажение имен в Python
  22. Экспорт данных с помощью writefile
  23. Операции с комплексными числами
  24. Форматирование объектов с модулем pprint
  25. Замеры производительности в Python
  26. Работа с модулем glob в Python
  27. Лямбда-функции в Python
  28. Многопоточность и асинхронное программирование в Python
  29. Метод hash в Python
  30. Retrying в Python: повторные вызовы
  31. Метаклассы в Python
  32. Подсчет часто встречающихся элементов
  33. Сортировка в Python
  34. Округление в Python
  35. Проверка окончания строки с помощью str.endswith()
  36. Метод lt для сортировки объектов
  37. Работа с файлами в Python
  38. Вычисление фазы комплексного числа
  39. Методы HTTP запросов в Flask
  40. Работа с парами ключ-значение
  41. Значения по умолчанию в Python
  42. Создание словарей с defaultdict
  43. Нан-рефлексивность в Python
  44. Подсчет частоты элементов с Counter
  45. f-строки в формате строк
  46. Работа с CSV файлами
  47. Логирование с Logzero: ротация файла

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

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