Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi.

Предположим, у нас есть массив a размерностью в 1000000 элементов и нам нужно в нем найти элемент key. Для простого, линейного поиска, эта задача решаема, но будет занимать довольно много времени. Именно для таких целей и существует бинарный поиск(bin Search).

В чем заключается его принцип? Бинарный поиск работает только на отсортированном массиве.
На каждом шаге мы берем средний элемент, затем сравниваем его с элементом левой и правом границы рассматриваемого участка(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);


Этот код выдаст нам на экран номер искомого элемента, если такой имеется.