Вход: упорядоченный массив А : array [l..n] of record k: key;i: info end record; ключ a: key.
Выход: индекс записи с искомым ключом а в массиве А или 0, если записи с таким ключом нет.
b: = 1 { начальный индекс части массива для поиска }
е: = n { конечный индекс части массива для поиска }
while b e do
с: =(b + е)/2 { индекс проверяемого элемента (округленный до целого) }
if A[c].k > a then
е:=с—1 { продолжаем поиск в первой половине }
else if A[c].k < a then
b: = с + 1 { продолжаем поиск во второй половине }
else
return с { нашли искомый ключ }
end if
end while
return 0 { искомого ключа нет в массиве }
обоснование
Для обоснования этого алгоритма достаточно заметить, что на каждом шаге основного цикла искомый элемент массива (если он есть) находится между (включительно) элементами с индексами b и е. Поскольку диапазон поиска на каждом шаге уменьшается вдвое, общая трудоемкость не превосходит log2 n.
9.4.4. Алгоритм поиска в дереве сортировкиСледующий алгоритм находит в дереве сортировки узел с указанным ключом, если он там есть.
Алгоритм 9.3. Поиск узла в дереве сортировки
Вход: дерево сортировки Т, заданное указателем на корень; ключ а.
Выход: указатель р на найденный узел или nil, если в дереве нет такого ключа.
р: = Т { указатель на проверяемый узел }
while р nil do
if a < p.i then
p:=p.l { продолжаем поиск слева }
else if a > p.i then
p : = p.r { продолжаем поиск справа }
else
return р { нашли узел }
end if
end while
обоснование
Этот алгоритм работает в точном соответствии с определением дерева сортировки: если текущий узел не искомый, то в зависимости от того, меньше или больше искомый ключ по сравнению с текущим, нужно продолжать поиск слева или справа, соответственно.
9.4.5. Алгоритм вставки в дерево сортировкиСледующий алгоритм вставляет в дерево сортировки узел с указанным ключом. Если узел с указанным ключом уже есть в дереве, то ничего не делается. Вспомогательная функция NewNode описана в подразделе 9.4.7.
Алгоритм 9.4. Вставка узла в дерево сортировки
Вход: дерево сортировки Т, заданное указателем на корень; ключ а.
Выход: модифицированное дерево сортировки Т.
if T = nil then
Т: = NewNode(o) { первый узел в дереве }
return Т
end if
p: = Т { указатель на текущий узел }
while true do
if a < p.i then
if p.l = nil then
q: = NewNode(a) { создаем новый узел }
p.l: = q { и подцепляем его к р слева }
return Т
else
p:=p.l { продолжаем поиск места для вставки слева }
end if
end if
if a > p.i then
if p.i = nil then
q : = NewNode(a) { создаем новый узел }
p.r:=q { и подцепляем его к р справа }
return Т
else
р: = р.г { продолжаем поиск места для вставки справа }
end if
end if
return Т { сюда попали, если уже есть такой ключ! }
end while
обоснование
Алгоритм вставки, в сущности, аналогичен алгоритму поиска: в дереве ищется такой узел, имеющий свободную связь для подцепления нового узла, чтобы не нарушалось условие дерева сортировки. А именно, если новый ключ меньше текущего, то либо его можно подцепить слева (если левая связь свободна), либо нужно найти слева подходящее место. Аналогично, если новый ключ больше текущего.
Наука измерения очень точна а такие измерения не точны и этого наука не любит