Бинарный поиск

Если массив данных отсортирован, то удается сократить время поиска, используя бинарный (метод деления пополам) поиск.

Отсортированность А позволяет, по результату сравнения со средним элементом массива, исключить из рассмотрения одну из половин. Далее применяем тот же прием по отношение к выбранной половине. Очевидно, не следует начинать поиск, если X>A[n] или X<A[1].

Программная реализация бинарного поиска может иметь следующий вид. Значением функции является индекс искомого элемента или ноль, если элемент не найден.

Const nmax=100;

Type vector=array[1..nmax] of Integer;

Var a:vector;

i, n: Integer;

X: Integer; {номер максимального элемента}

Function bin( Var A: vector; n, X: integer): integer ;

{двоичный поиск X в массиве A, n – размер массива}

Var i, j, m: Integer;

f: Boolean;

Begin

i:=1; j:=N;

{Ha первом шаге рассматривается весь массив}

f:=False; {Признак того, что X не найден}

While (i<=j) And Not f Do Begin

m:=(i+j) Div 2;

If A[m]=X Then f:=True {Элемент найден}

Else

If A[m]<X Then i:=m+1 {*Исключаем левую часть}

Else j:=m-1; {*Правую часть.*}

End;

if f then bin:=m else bin:=0;

End;

Begin{основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

Write( bin( a, n, X));

Readln

End.

Предложим еще одну, рекурсивную, реализацию изучаемого поиска[2]. Значением переменной t является индекс искомого элемента или ноль, если элемент не найден.

Const nmax=100;

Type vector=array[1..nmax] of Integer;

Var a: vector;

i, n, t: Integer;

X: Integer;

Procedure bin(i, j :Integer; Var t: Integer);

{i и j – диапазон поиска, t результат }

{A и X глобальные переменные}

Var m: Integer;

Begin

If i>j Then t:=0

Else Begin

m:=(i+j) Div 2;

If A[m]<X Then bin(m+1, j, t)

Else

If A[m]>X Then bin(i, m-1, t)

Else t:=m;

End;

End;

Begin {основная программа}

Write ('размер массива='); Readln(n);

Write ('Вводите элементы массива столбиком');

For i:=1 to n do Readln(a[i]);

Write ('искомое число='); Readln(X);

bin(1, n, t); {при первом обращении – весь массив}

Write(t);

Readln

End.