1
( ). . . .
1.
n . , , L.
: ?
L , .
: 2 :
: k:= , L
: k:=0
2.
n . , , L.
,
:
2 3 5 7 8 10 11 15 16
1 2 3 4 5 6 7 8 9
: []=L
-
?
?
= {1,..,9} =0
. ()
L<A[1] L>A[n] Ak <L<Ak+1
k+1 k = 1
[k, k+1] .
?
1) 1 ( )
,
2) 1
3) : c [1, n].
:
1
: 2 : , , - ,
.
1 2 ?
, . . = [] , . . , . . < 1.
. [1] < A[2] < .<A[n]
[ .a....k ][ k+1.... b ]
[1, n] [a, b]
k.
L A[k]
. ., , L
| L Î [1, k] ? L <= A[k] [a, b] b:=k | L Î [k + 1, n] ? L <= A[k] [a, b] a:=k+1 |
, ,
:
k [, b]
k=(a + b)/2
: ( )
1) L A[]
2)
3)
, L< > A[k] . b a>=1
?
. ?
1. L = A[k] 2. b a < 1
|
|
|
, A[k] < > L
k.
A[k] , k:=0.
k 0 , .
: , , [A[1], A[n]]
Þ :=0
Þ (n, A, L, k)
:
n - -
L
.
L Î [[1], [n]]
:=0 (n, A, L, k)
ß
k
k:=0 k
= 1
b = n
k = (a + b )/ 2 - [, b]
n = 9 ( )
| - |
L = 1, 17
2, 16
L = 3, 15
8
12, 4
N .
? = Log2 N
, , *Log2 N = (Log2 N)
, , - , .
, . , , .
, , . , , .
() - () n - (), n-1 - .
, , :
1. ;
2. ;
3. ;
4. .
.
1. , . , , , , , , .. .
2. , , .
|
|
|
3. - . , , . , .
4. . , , , . , , . , .
: ,
