Линейный поиск

Описание

Суть линейного поиска состоит в том, что поочерёдно сверяются значения элементов массива с искомым значением, пока не достигнут конец массива.
Допустим, x - искомое значение в массиве A целых чисел размера N элементов.

Условиями поиска являются:

  1. проверка выхода за границы массива (i ⇐ N)
  2. проверка, является ли текущий элемент искомым (A[i] <> x)

Итак, алгоритм таков:

Установить счётчик в начальное положение
Цикл Пока (не достигнут конец массива) И (Элемент массива не явдяется искомым) Выполнять
  Увеличение счётчика

или на Паскале:

    i := 1;
    while (i <= N) And (A[i] <> x) do
      Inc (i);

Таким образом, искомый элемент x считается найденным в массиве A, если индекс позиции i находится в пределах 1..N. Если же i > N, то элемент не был найден в массиве.

Пример

const
    N = 12;
type
    TArr = array[1..N] of integer;
 
{ заполнение массива случайными значениями }
procedure GenArrayVal (var V: TArr; const n: integer);
var
    k: integer;
begin
    randomize;
    for k := 1 to N do
        V[k] := random(10);
end;
 
{ вывод на экран массива }
procedure PrintArrayVal (var V: TArr; const n: integer);
var
    i: integer;
begin
    for i := 1 to N do
        write (V[i]:4);
    writeln;
end;
 
{ линейный поиск }
function LinearSearch (x: integer; A: TArr): integer;
var
    i: integer;
begin
    i := 1;
    while (i <= N) And (A[i] <> x) do
      Inc (i);
    LinearSearch := i
end;
 
var
    V: TArr;
    x, i: integer;
begin
    GenArrayVal (V, N);
    PrintArrayVal (V, N);
 
    x := 5; { искомое значение }
 
    i := LinearSearch (x, V);
 
    if i > N then
        writeln (x, ' не найден.')
    else
        writeln (x, ' найден у позиции #', i)
end.
 
pascal/search/linear.txt · Последние изменения: 2009/10/30 20:15 От romtek
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki