1

Учу алгоритмы и узнал, что бинарный поиск применяется только к отсортированному списку элементов, но не написано почему нельзя использовать неотсортированный. Можете объяснить почему?

1
  • 6
    А как вы представляете себе работу бинарного поиска на неотсортированном списке?
    – andreymal
    22 июн 2019 в 10:01

1 ответ 1

7

Алгоритм двоичного поиска предполагает итеративное деление списка пополам, где на каждом шаге искомый элемент сравнивается со значением среднего элемента в отсортированном списке. Если искомый элемент меньше среднего элемента - значит дальше искать будем в первой половине, если больше, то во второй половине, если равен то мы нашли искомый элемент.

Если список не отсортирован, то невозможно воспользоваться алгоритмом половинного деления, т.к. искомый элемент может оказаться в любой половине списка.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.