Бинарный поиск — наиболее известная техника поиска в мире программирования. Существенным преимуществом бинарного поиска является то, что он быстрее, чем метод линейного поиска. Итак, давайте поговорим о его алгоритме.
Алгоритм:
Первое, что важно в бинарном поиске, это массив, в котором реализован бинарный поиск, должен быть отсортированным массивом. Двоичный поиск не будет работать с несортированным массивом.
В двоичном формате мы сначала сравниваем средний элемент массива с элементом, который необходимо найти. Если средний элемент и целевой элемент совпадают, просто верните средний индекс. Если они не совпадают, проверьте, больше или меньше целевое значение среднего элемента.
Если целевой элемент меньше среднего элемента, мы движемся к левой части массива, а если он больше среднего элемента, мы двигаемся к правой части массива. Поскольку список отсортирован, поэтому целевой элемент не может находиться на других сторонах массива в зависимости от сравнения со средним элементом.
После этого мы сравниваем его со средним элементом этой части и выполняем ту же процедуру до тех пор, пока элемент не будет найден, или, если мы сжимаемся до размера только одного элемента, и в этом случае мы просто возвращаем -1, что означает цель элемент не найден.
Анализ:
Как я уже говорил ранее, бинарный поиск быстрее, чем линейный поиск, потому что он просто сокращает массив и сужает область поиска.
Таким образом, в лучшем случае временная сложность бинарного поиска составляет O (1), а в худшем случае его временная сложность составляет O (log n), что намного меньше, чем временная сложность линейного поиска O (n).
Код :
Вот код для рекурсивного и итеративного двоичного поиска в C++.
