Структура данных - массив. Часть 1 - 15 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

15
Сложность этого алгоритма порядка log
2
(n) .
С помощью этого алгоритма можно определить, содержится ли в мас-
сиве заданный элемент x и каков его номер (k). Для того, чтобы определить
отрезок, на котором находится x , эффективней воспользоваться алгоритмом,
который опишем в виде функции
search_Bin.
const n_max=20;
type vect=array[1..n_max] of integer;
function search_Bin(n:integer; const a:vect;
x:integer):integer;
var i,j:integer;
begin
if (a[1]> x) then j:=0;
if (a[n]<= x) then j:=n;
if (a[1]<= x) and (a[n]> x) then
begin
i:=1; j:=n;
repeat
k:=(i+j) div 2;
if a[k] <= x then i:=k+1;
if a[k] >= x then j:=k-1
until (i>j);
if a[k]= x then j:=k
end;
search_Bin:=j
end;
Этот алгоритм определяет отрезок, которому принадлежит заданный
элемент
x, а именно, x∈[a[j];a[j+1]), 1≤j<n. Если x=a[j], то
j – индекс значения x в массиве.
3.3. Операции, изменяющие состояние массива
К операциям, изменяющим состояние массива, относятся следующие:
изменить, вставить, добавить, удалить элементы.

Страницы