Бинарный поиск - один из самых простых способов нахождения элемента в массиве

Довольно часто программисты, даже начинающие, сталкиваются с тем, что есть набор чисел, в котором необходимо найти определенное число. Вот эту коллекцию называют массивом. А чтобы найти нужный элемент в нем, есть огромное множество способов. Но самым простым среди них по праву можно считать бинарный поиск. В чем же заключается данный метод? И как реализовать бинарный поиск? Паскаль является самой простой средой для организации такой программы, поэтому будем использовать именно его для изучения.

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

Итак, в чем же заключается принцип работы данного метода? Сразу стоит сказать, что работает бинарный поиск не в любом массиве, а только в отсортированном наборе чисел. На каждом следующем шаге берется средний элемент массива (имеется в виду по номеру элемента). Если искомое число больше среднего, значит все то, что находится слева, то есть меньше среднего элемента, можно отбросить и не искать там. И наоборот, если меньше среднего – среди тех чисел, что справа, можно не искать. Дальше выберем новую область поиска, где первым элементом станет средний элемент всего массива, а последний так и останется последним. Средним же числом новой области станет ¼- всего отрезка, то есть (последний элемент + средний элемент всего массива)/2. Опять производится та же операция – сравнение со средним числом массива. Если искомая величина меньше среднего, отбрасываем правую часть, и так же делаем дальше, пока вот этот средний элемент не окажется искомым.

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

В ней будет массив от 1 до h под названием "massiv", переменная, обозначающая нижнюю границу поиска, названная "niz", верхняя граница, названная "verh", средний элемент поиска - "sredn"- и искомое число - "isk".

Итак, сначала назначаем верхнюю и нижнюю границы интервала поиска:

niz:= 1-
verh:= h + 1-

Затем организовываем цикл "пока нижняя меньше верхней границы":

While niz < verh - 1 do
begin

На каждом шаге делим отрезок на 2:

sredn:= (niz + verh) div 2- {используем функцию div, потому что делим без остатка}

Каждый раз проводим проверку. Если средний равен искомому, прерываем цикл, так как нужный элемент уже найден:

іf sredn=isk then break-

Если средний элемент массива больше искомого, отбрасываем левую часть, то есть верхней границей назначаем средний элемент:

if massiv [sredn] > isk then verh:= sredn-

А если наоборот, то его делаем нижней границей:

else niz := sredn-
end-

Вот и все, что будет в программе.

Разберем, как будет выглядеть бинарный метод на практике. Возьмем такой массив: 1, 3, 5, 7, 10, 12, 18 и будем искать в нем число 12.

Всего у нас 7 элементов, поэтому средним будем четвертый, его значение 7.

Так как 12 больше 7, элементы 1,3 и 5 мы можем отбросить. Дальше у нас осталось 4 числа, 4/2 без остатка равно 2. Значит, новым средним элементом будет 10.

Так как 12 больше 10, отбрасываем 7. Остается только 10, 12 и 18.

Здесь средний элемент уже 12, это и есть искомое число. Задача выполнена – число 12 найдено.