Очевидно, что нельзя каким-либо способом ускорить поиск, если отсутствует информация о данных, среди которых производится поиск. Также известно, что если данные упорядочены, то поиск можно сделать значительно эффективнее. Поэтому рассмотрим алгоритм, который основан на том, что массив A упорядочен (т. е. a[i-1] <= a[i] при 1 <= i < N).

     Суть: берут средний элемент массива и сравнивают его с ключом. В результате возможны 3 случая:

     1) если элемент массива равен ключу, то искомый элемент найден;

     2) если элемент массива меньше ключа, то все элементы массива с индексами, которые меньше N/2 исключаются из рассмотрения;

     3) если элемент массива больше ключа, то все элементы массива с индексами, которые больше N/2 исключаются из рассмотрения;

     Затем поиск продолжается в одной из половин массива аналогичным образом.

{bin.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

const N=10;

type Any=integer;

var A:array[0..N] of Any;

       Left,Right,m,i,j:integer;

       b:Any;

begin

  writeln('Введите упорядоченную последовательность эл-тов массива ');

  for i:=0 to N do readln(A[i]);

  writeln('Введите ключ');

  readln(b);

  Left:=0;Right:=N;

  while Left < Right do

   begin

     m:=(Left+Right) div 2;

     if A[m] < b then Left:=m+1

                       else Right:=m;

  end;

  if (Right<>N) or ((Right=N) and (a[N]=b)) then writeln('Эл-т найден. Позиция эл-та: ',Right)

                                                                   else writeln('Элемента нет');

end.

     Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log2(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного - как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства этого приведем следующие характеристики линейного и бинарного поиска:

1) линейный поиск:

• количество элементов:10

• среднее количество сравнений при наличии элемента:5

• количество сравнений при отсутствии элемента:10

• количество элементов:1000

• среднее количество сравнений при наличии элемента:500

• количество сравнений при отсутствии элемента:1000

• количество элементов:1000000

• среднее количество сравнений при наличии элемента:500000

• количество сравнений при отсутствии элемента:1000000

2) бинарный поиск:

• количество элементов:10

• максимальное количество сравнений при наличии элемента:8

• максимальное количество сравнений при отсутствии элемента:8

• количество элементов:1000

• максимальное количество сравнений при наличии элемента:10

• максимальное количество сравнений при отсутствии элемента:10

• количество элементов:1000000

• максимальное количество сравнений при наличии элемента:20

• максимальное количество сравнений при отсутствии элемента:20