Оглавление:
Определение - что означает бинарный поиск?
Алгоритм двоичного поиска используется для поиска позиции определенного значения, содержащегося в отсортированном массиве. Работая по принципу «разделяй и властвуй», этот алгоритм поиска может быть довольно быстрым, но предостережение заключается в том, что данные должны быть в отсортированном виде. Это работает, начиная поиск в середине массива и работая вниз по первой нижней или верхней половине последовательности. Если медианное значение ниже, чем целевое значение, это означает, что поиск должен идти выше, если нет, то он должен смотреть на нисходящую часть массива.
Бинарный поиск также известен как полуинтервальный поиск или логарифмический поиск.
Техопедия объясняет бинарный поиск
Бинарный поиск - это быстрый и эффективный метод поиска определенного целевого значения из набора упорядоченных элементов. Начав с середины отсортированного списка, он может эффективно сократить пространство поиска пополам, определив, следует ли увеличивать или уменьшать список на основе медианного значения по сравнению с целевым значением.
Например, с целевым значением 8 и пространством поиска от 1 до 11:
- Медиана / среднее значение найдено, и указатель установлен там, который в этом случае равен 6.
- Цель 8 сравнивается с 6. Поскольку 6 меньше 8, цель должна быть в верхней половине.
- Указатель перемещается к следующему значению (7) и сравнивается с целью. Он меньше, поэтому указатель перемещается к следующему более высокому значению.
- Указатель теперь на 8. Сравнивая это с целью, это точное совпадение, поэтому цель была найдена.
Используя бинарный поиск, цель нужно было сравнить только с тремя значениями. По сравнению с линейным поиском он начинался бы с самого первого значения и перемещался вверх, что требовало сравнения цели с восемью значениями. Бинарный поиск возможен только с упорядоченным набором данных; если данные расположены случайным образом, то линейный поиск будет давать результаты все время, в то время как двоичный поиск, вероятно, застрянет в бесконечном цикле.
