Поиск наименьшего (наибольшего) элемента в линейном массиве.

Последовательный поиск в линейном массиве.

Поиск элементов линейного массива, удовлетворяющих определенному условию.

Введение.

Тема 11. Алгоритмы поиска (в линейных массивах).

While not eof(filer) do

Begin

Read(filer,buf);

Write(buf,‘ ‘);

End;

Close(filer);

End.

Поиск является одной из наиболее часто встречающихся задач в программировании.

Общая задача поиска.

Пусть имеется фиксированное множество элементов P и задан критерий поиска K. Необходимо найти среди всех элементов P те, которые удовлетворяют K.

Существует множество алгоритмов поиска, мы рассмотрим некоторые из них на примере линейных массивов.

Идея алгоритма: необходимо просмотреть элементы массива от первого до последнего, проверить выполнение условия для каждого из них и выполнить некоторые действия, если условия истины. В большинстве случаев необходимо не получить требуемые элементы, а найти их количественную характеристику (количество, сумму, произведение и т.д.).

Общий вид:

A – массив из p элементов,

k – условие.

For i:=1 to p do

if k then <действие>;

где <действие> - совокупность операторов.

Постановка задачи: необходимо определить содержится ли в линейном массиве размера p элемент равный заданному.

Идея: будем рассматривать элементы массива до тех пор пока не найдем совпадения или не достигнем конца массива.

Общий вид:

type TRealMas=array[1..p] of real;

Function FindEquals(a:TRealMas;p:integer;x:real):boolean;

var i:integer;

temp:boolean;

begin

temp:=false;

i:=1;

while (i<=p)and(temp=false) do

if a[i]=x then temp:=true

else i:=i+1;

FindEquals:=temp;

end.

В процессе поиска будет произведено определенное количество сравнений. Попытаемся оценить его. Рассмотрим величины M_min – минимальное количество шагов алгоритма, M_max – максимальное количество шагов алгоритма, M_ср. – среднее количество шагов алгоритма.

В нашем случае:

S=p*(p+1)/2

M_min=1

M_max=p

M_ср.=S/p=(p+1)/2.

Под M_ср. понимают количество шагов "в среднем случае", т.е. наиболее вероятное количество шагов.

Пусть задан массив A, наибольшим (наименьшим) элементом назовем такой элемент a[k], что для любого iÎ1..p, если i¹k то a[i]£a[k].

Постановка задачи: необходимо определить первый из наименьших (наибольших) элементов линейного массива размера p и указать его номер.

Построим процедуру, находящую наибольший элемент линейного массива и его номер.

Procedure FindMax(A:TrealMas; p:integer: var max: real; var Nmax:integer);

Var i:integer;

Begin

Max:=a[1];

Nmax:=1;

For i:=2 to p do

If a[i]>max then

Begin

Max:=a[i];

Nmax:=i;

End;

End.