Алгоритм бинарного поиска: функция, преимущества, временная и пространственная сложность

Введение

В любой вычислительной системе поиск является одной из наиболее важных функций, которые необходимо разработать. Методы поиска используются при поиске файлов, индексировании и многих других приложениях. Существует множество методов поиска. Одним из них является метод бинарного поиска.

Алгоритм бинарного поиска основан на идее игнорирования половины списка на каждой итерации. Он продолжает разбивать список, пока не найдет искомое значение в заданном списке. Алгоритм бинарного поиска — это быстрый апгрейд простого алгоритма линейного поиска.

Опыт кодирования не требуется. Карьерная поддержка на 360°. Диплом PG в области машинного обучения и искусственного интеллекта от IIIT-B и upGrad.

Работа алгоритма бинарного поиска

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

• Если желаемое значение равно ценности центрального индекса, то индекс возвращается в качестве ответа.

• Если целевое значение меньше, чем значение центрального индекса списка, то правая часть списка игнорируется.

• Если желаемое значение больше, чем значение центрального индекса, то левая половина отбрасывается.

• Затем процесс повторяется для укороченных списков, пока не будет найдено целевое значение.

Пример №1

Рассмотрим алгоритм на примере. Предположим, что имеется список со следующими номерами:

1, 15, 23, 7, 6, 14, 8, 3, 27

Примем искомое значение за 27. Общее количество элементов в списке равно 9.

Первым шагом является сортировка списка. После сортировки список будет выглядеть примерно так:

1, 3, 6, 7, 8, 14, 15, 23, 27

Поскольку количество элементов в списке равно девяти, центральный индекс будет равен пяти. Значение в индексе пять равно 8. Искомое значение 27 сравнивается со значением 8. Сначала проверьте, равно ли значение 8 или нет. Если да, вернуть индекс и выйти.

Поскольку 27 больше 8, мы бы проигнорировали левую часть и прошлись только по правой стороне списка. Новый список для прохождения:

14, 15, 23, 27

Примечание. На практике список не усекается. Только наблюдение сужается. Таким образом, «новый список» не следует путать с созданием нового списка или сокращением исходного. Хотя это можно было бы реализовать с помощью нового списка, есть две проблемы. Во-первых, будут накладные расходы памяти. Каждый новый список будет увеличивать сложность пространства. Во-вторых, исходные индексы необходимо отслеживать на каждой итерации.

Новый центральный индекс можно использовать как второй или третий элемент, в зависимости от реализации. Здесь мы будем считать третий элемент центральным. Значение 23 сравнивается со значением 27. Поскольку значение больше центрального значения, мы отбрасываем левую половину.

Список для прохождения:

27

Поскольку список содержит только один элемент, он считается центральным элементом. Следовательно, мы сравниваем желаемое значение с 27. Когда они совпадают, мы возвращаем значение индекса 27 в исходном списке.

Пример #2

В том же списке предположим, что желаемое значение равно 2.

Во-первых, центральное значение восемь сравнивается с 2. Поскольку желаемое значение меньше центрального значения, мы сужаем фокус до левой части списка.

Новый обход будет состоять из:

1, 3, 6, 7

В качестве второго элемента возьмем центральный элемент. Искомое значение два сравнивается с 3. Поскольку значение все еще меньше, мы снова сужаем фокус до левой части списка.

Новый обход будет состоять из:

1

Поскольку список обхода имеет только один элемент, значение напрямую сравнивается с оставшимся элементом. Мы видим, что значения не совпадают. Следовательно, мы выходим из цикла с сообщением об ошибке: значение не найдено .

Расширенная сертификация Data Science, более 250 партнеров по найму, более 300 часов обучения, 0% EMI

Сложность времени и пространства

Временная сложность алгоритма бинарного поиска составляет O(log n). В лучшем случае временная сложность будет O(1), когда центральный индекс будет напрямую соответствовать желаемому значению. Наихудшим сценарием могут быть значения на краю списка или значения, не входящие в список.

Пространственная сложность алгоритма бинарного поиска зависит от реализации алгоритма. Есть два способа его реализации:

1. Итерационный метод
2. Рекурсивный метод

Оба метода совершенно одинаковы, с двумя отличиями в реализации. Во-первых, в рекурсивном методе нет цикла. Во-вторых, вместо того, чтобы передавать новые значения в следующую итерацию цикла, он передает их в следующую рекурсию. В итеративном методе итерации можно контролировать с помощью условий зацикливания, а в рекурсивном методе в качестве граничного условия используются максимум и минимум.

В итеративном методе пространственная сложность будет O (1). В то время как в рекурсивном методе пространственная сложность будет O (log n).

Преимущества

• Алгоритм двоичного поиска является довольно простым для реализации алгоритмом поиска.

• Это значительное улучшение по сравнению с линейным поиском, и его эффективность почти такая же, как у некоторых более сложных алгоритмов поиска.

• Алгоритм бинарного поиска разбивает список пополам на каждой итерации, а не последовательно прочесывает список. В больших списках этот метод может быть очень полезен.

Оформить заказ: классификация дерева решений: все, что вам нужно знать

Заключение

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

Если вам интересно узнать о науке о данных, ознакомьтесь с дипломом IIIT-B & upGrad PG в области науки о данных, который создан для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1- on-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.