. , , .. (). , (, ) (, ) . . . .
"". , .
. , : , . : , . : . , .
. , . ( ), . , . . , . .
""
" ". . . , . .
: , , , . , : . , , , .
, . .
- . , . .. (l, u - ):
1.[ ] l 1, u N.
A2.[ ] u<l, . i [(l+u)/2].
|
|
A3.[] K<Ki, 4, >Ki, - 5, =Ki, .
4.[ u] u i-1 2.
5.[ l] l i+1 2.
N , .
- l,u,i - i . . :
B1. [ ] i [N/2], m {N/2}.
B2. [] < i 3. >Ki, - 4, =Ki, .
3. [ i] m=0, . i i-[m/2], m {m/2} 2.
4. [ i] m=0, . i i+[m/2], m {m/2} 2.
([x] - , {x} - , )
, ( ) , - l. , . , , . , N, N.