Практика программирования (Бейсик, Си, Паскаль)




Поиск - часть 2


Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится q. Теперь цикл повторяется до тех пор, пока не будет встречен элемент а [ j ], равный q, и необходимость в проверке j < n + 1 отпадает. Конечно, перед возвратом из процедуры надо удостовериться в том, что найденный индекс j не равен n + l. Но такая проверка выполняется за пределами цикла.

Для программистов, имеющих дело с языком ассемблера, известен и более простой прием, не требующий расширения исходного массива. Очевидно, цикл поиска можно организовать как в прямом (j меняется от 1 до n), так и в обратном (j меняется от n до i) направлении. Обратный цикл на ассемблере реализуется с помощью команды LOOP, организующей возврат в начало цикла с одновременным вычитанием 1 из счетчика сх. Цикл повторяется до тех пор, пока содержимое регистра сх не станет равным 0. Таким образом, дополнительного сравнения (j < n + 1) здесь не требуется.

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

Функция ssearch.bas

FUNCTION SSEARCH(Q,A(),N)

FOR J=0 TO N-l

IF Q=A(J) THEN SSEARCH=J: EXIT FUNCTION

NEXT J

SSEARCH=-1

END FUNCTION

Функция ssearch.c

int ssearch(int q, int *a, int n)

}

register int j;

for(j=0; j<n; j++)

if(q==a[j]) return j;

return -1;

}

Функция ssearch.pas

function ssearch(q:integer;a:array of integer;n:integer):integer;

var

j:integer; begin

for j:=0 to n-1 do

if q=a[j] then

begin

ssearch:=j;

exit;

end;

ssearch:=-l;

end;

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

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




Содержание  Назад  Вперед