Предположим, у нас есть массив a размерностью в 1000000 элементов и нам нужно в нем найти элемент key. Для простого, линейного поиска, эта задача решаема, но будет занимать довольно много времени. Именно для таких целей и существует бинарный поиск(bin Search).
В чем заключается его принцип? Бинарный поиск работает только на отсортированном массиве.
На каждом шаге мы берем средний элемент, затем сравниваем его с элементом левой и правом границы рассматриваемого участка(l, r). Соответственно, если элемент, который мы выбрали, оказывается меньше искомого, то можно отбросить левую часть рассматриваемого участка, так как и все элементы, которые там находятся будут меньше искомого.
Пример:
Ищем 15 в массиве: 6, 8, 9, 13, 15, 17.
1 шаг: берем средний элемент, то есть 13.
2 шаг: смотрим, больше ли этот элемент искомого, нет. Значит отбросим все элементы, идущие до среднего, так как они заведомо меньше(массив отсортирован!).
3 шаг: Остались только числа 13, 15, 17. Берем средний элемент, и вот он, 15.
В бинарном поиске может быть большое количество шагов до совпадения, но меньше, чем в линейном.
Этот код выдаст нам на экран номер искомого элемента, если такой имеется.
В чем заключается его принцип? Бинарный поиск работает только на отсортированном массиве.
На каждом шаге мы берем средний элемент, затем сравниваем его с элементом левой и правом границы рассматриваемого участка(l, r). Соответственно, если элемент, который мы выбрали, оказывается меньше искомого, то можно отбросить левую часть рассматриваемого участка, так как и все элементы, которые там находятся будут меньше искомого.
Пример:
Ищем 15 в массиве: 6, 8, 9, 13, 15, 17.
1 шаг: берем средний элемент, то есть 13.
2 шаг: смотрим, больше ли этот элемент искомого, нет. Значит отбросим все элементы, идущие до среднего, так как они заведомо меньше(массив отсортирован!).
3 шаг: Остались только числа 13, 15, 17. Берем средний элемент, и вот он, 15.
В бинарном поиске может быть большое количество шагов до совпадения, но меньше, чем в линейном.
- Код:
l := 1;
r := n + 1;
While l < r - 1 do
begin
m := (l + r) div 2;
if a[m] > key then r := m
else l := m;
end;
if a[l] = key then WriteLn(l);
Этот код выдаст нам на экран номер искомого элемента, если такой имеется.
Ср Окт 12, 2016 2:43 am автор SeriousPasha
» требуется несколько JS разработчиков
Пт Окт 07, 2016 10:19 pm автор mrktwn1
» Защита приложения от взлома
Чт Июн 18, 2015 10:28 pm автор stradi
» Ищите программиста или дизайнера?
Пт Мар 27, 2015 6:25 am автор фриланс
» Создание и продвижение сайтов, их развитие.
Ср Мар 25, 2015 12:40 am автор asdfghhgfdsa
» Исходники для студентов + скайп-консультации,помощь в написании программ
Вт Окт 07, 2014 11:25 pm автор Horpion
» IT- технологии для развития бизнеса
Пн Июн 23, 2014 6:11 pm автор dvos12
» Стенли Кубрик "С Широко закрытыми Глазами"
Чт Июн 12, 2014 2:01 am автор Vertuozzz
» Каталог популярных хостинг компаний
Сб Май 10, 2014 7:18 pm автор naik