, . - AM . AM=, ; AM <X, , , , . , AM >X.
, . . , - . , .. .
, . 5.7. 52. 49. 49<52, , 49. 86. 86>52, 52 , 86, 49. , 52. .
:
Low = 1 hi = n while (low <= hi) do mid = (low + hi) div 2 if key = k(mid) then search = mid return endif if key < k(mid) then hi = mid - 1 else low = mid + 1 endif endwhile search = 0 return | low:= 1; hi:= n; while (low <= hi) do begin mid:= (low + hi) div 2; if key = k[mid] then begin search:= mid; exit; end; if key < k[mid] then hi:= mid - 1 else low:= mid + 1; end; search:= 0; exit |
key = 101 ( ).
- , n - , = log2n.
, n = 1024.
= 512, = 10.
- ( ), , .
, . . , , . 5.8.
, , .. N/2 .
, . log2N .
- , , , .
.
.
. . , , - .
key
p = tree whlie p <> nil do if key = k(p) then search = p return endif if key < k(p) then p = left(p) else p = right(p) endif endwhile search = nil return | p:= tree; whlie p <> nil do begin if key = p^.k then begin search:= p; exit; end; if key < p^.k then p:= p^.left else p:= p^.right; end; search:= nil; |