Практика программирования (Бейсик, Си, Паскаль)
а добавляется еще один элемент,
Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится 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;
Бинарный поиск
Бинарный поиск, суть которого была раскрыта выше на примере поимки льва в пустыне, применяется только для предварительно упорядоченных массивов. Несмотря на абсолютную прозрачность идеи деления пополам, ее программная реализация требует большой аккуратности как в использовании сравнений, так и в выборе очередного интервала поиска.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий