Курс 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. Изменение элемента списка
  3. Тестирование функции сложения
  4. Функция enumerate() в Python
  5. Обрезка изображения с Pillow
  6. Блок else в Python
  7. Сложение матриц в NumPy
  8. Сортировка данных в Python
  9. Переворот строки с использованием цикла
  10. Методы shutil для работы с файлами
  11. Цикл for в Python
  12. Оптимизация строк в Python
  13. Определение локальных переменных в Python
  14. GitHub в Telegram: подписка на уведомления
  15. Итерация по коллекции в Python
  16. Генераторы в Python
  17. Работа с необработанными строками
  18. Измерение времени выполнения кода с использованием time
  19. Работа с итераторами в Python
  20. Непрерывная проверка в Python
  21. Хеши в Python
  22. Создание словарей и множеств в Python
  23. Множественное назначение в Python
  24. Статическая типизация в Python
  25. Пересечение списков с использованием множеств
  26. Удаление символов новой строки в Python.
  27. kwargs в Python
  28. Проверка элементов списка условием
  29. Регулярные выражения: метод match
  30. Подсчет количества элементов в списке
  31. Форматирование строк в Python
  32. Инверсия списка/строки в Python
  33. Конкатенация строк с помощью join()
  34. Применение функций в Python
  35. Генерация случайных чисел Python
  36. Функции any() и all() в Python
  37. Подробная информация о %pinfo
  38. Обработка исключений в Python
  39. Подсказки типов в Python
  40. Генератор списка с условием if
  41. Работа со строками в Python
  42. Частичное совпадение ввода
  43. Расчет времени выполнения кода
  44. Быстрый поиск кода
  45. Аннотации типов в Python
  46. Метод setdefault() в Python
  47. Константы в модуле cmath
  48. Метод округления чисел

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

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