П О И С К В У П О Р Я Д О Ч Е Н Н О М М А С С И В Е

Рассматривается массив целых чисел, сгруппированных по возрастанию (или убыванию). При этом предполагается, что в данном массиве нет повторяющихся элементов, т.е. строго выполняется отношение . Требуется для заданного целочисленного значения определить индекс элемента . Если в массиве нет элемента, равного значению , то присвоить переменной нулевое значение.

Такая задача поиска часто возникает в системах АСУ, САПР и других при выборке информации из различных архивов. Самым простым методом для ее решения является метод прямого перебора, или, как его еще называют, метод линейного поиска. При использовании указанного метода последовательно просматриваются элементы массива до тех пор, пока не будет найден искомый элемент или не станет ясно, после просмотра всего массива, что такого элемента здесь нет.

ProgramDirectSearch;

ConstNmax = 500;

Type Ar = array[1..Nmax] of word;

Var i,k,n,b : word;

X : Ar;

Begin

Ввод и печать n,X,b

k:=0;

For i:=1 ton do

Ifx[i]=b then

Begin

k:=i; Break

End;

Печать k

End.

Если , то в массиве анализируется лишь один элемент; если или в массиве отсутствует элемент, равный значению , то анализируются элементов. Среднее количество просмотров элементов массива равно .

Если массив неупорядочен, то метод прямого перебора является единственно возможным. Для упорядоченного массива наиболее эффективным является метод двоичного (бинарного) поиска.

Пусть массив имеет элементов. Сущность алгоритма двоичного поиска сводится к следующему.

1) Рассматривается диапазон поиска . Левая граница диапазона , правая граница . Выходной переменной присваивается нулевое начальное значение.

2) Если , поиск прекращается.

3) Определяется , т.е. индекс середины диапазона.

4) Если , поиск закончен, переменной присваивается значение m . В противном случае - переход к шагу 5.

5) Если , то это означает, что в правой половине подмассива (от m+1 до ) не может быть элемента, равного b. Тогда граница перемещается в точку m-1: . При этом диапазон поиска уменьшается вдвое. Дальше - переход к шагу 2.

6) Если , то аналогичным образом к точке m+1 сдвигается левая граница : . В этом случае диапазон поиска также уменьшается вдвое и производится переход к шагу 2.

Если в массиве нет элемента, равного , то после нескольких шагов возникает ситуация , что ведет к прекращению работы алгоритма. В этом случае выходная переменная сохраняет начальное значение .

Примечание. Выполнять в пп.5 и 6 переход в точку m нет смысла, так как элемент уже был проверен.

Program BinarySearch;

Const Nmax = 500;

TypeAr = array[1..Nmax] ofinteger;

Vari1,i2,k,n,m,b : integer;

X : Ar;

Begin

Ввод и печать n,X,b

i1:=1; i2:=n; k:=0;

While i1<=i2 do

Begin

m:=(k1+k2) div2;

If x[m]=b then

Begin

k:=m; Break

End;

Ifx[m]>b then

i2:=m-1

Else

i1:=m+1;

End;

Печать k

End.

Cреднее количество просмотров элементов массива в методе двоичного поиска равно , что значительно меньше значения .