ВУЗ:
Составители:
14
begin
if a[1]>x then search_Lin:=0;
if a[n]<=x then search_Lin:=n;
if (a[1]<= x) and (x<a[n]) then
begin
i:=1;
while (a[i+1]≤x) do
i:=i+1;
search_Lin:=i
end
`end;
Сложность линейных алгоритмов определяется количеством элемен-
тов в массиве и записывается так O(n) (читается: порядка n). Сложность оп-
ределяет затраты на выполнение циклического процесса.
Задача 4. Поиск элемента в упорядоченном массиве. Бинарный поиск.
Метод решения.
Найдем середину массива − индекс k.
Сравним a[k] и x. Возможны три случая:
1
) a[k] = x − искомый элемент найден;
2)
a[k] < x − искомый элемент находится в правой части массива;
3)
a[k] > x − искомый элемент находится в левой части массива.
Описание алгоритма.
i:=1; j:=n
q:=false;
repeat
k:=(i+j) div 2;
if a[k] = x then q:=true
else if a[k] < x then i:=k+1
else i:k-1
until q or (i>j);
Этот алгоритм называется бинарным поиском (или двоичным поиском, или дихо-
томическим поиском).
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
