, , . log2n, n . , , (n) = log2n.
2 . , . , -. . , , (, ).
, . 1.
1. ().
2.
.
3. .
( ) . . .
.
1.1. (n).
1.2. .
1.3. (i) 0 n
1.3.1. [i].
2. :
2.1. (k) 1 n - 1
2.1.1. (i) 0 n - k
[ i ] > [ i +1],
[i] [i+1].
3.
3. 1. ( );
3. 2. ,
3.2.1 _ ( ) = 0;
3.2.2. _ ( ) = n - 1 (. 1);
3.2.3. = [ n - 1],
a) = ;
b) k = n 1.
3.2.4. = .
3.2.5.
a) k = ((_ + _)/2);
b) = [ k ],
:=
> [ k ],
_ = k
_ = k.
(_ = _ - 1).
3.3. ,
: k,
: .
.
4. .
3.2.3 . , 2 , 1 , .
, . 0 99. , , .
|
|
|
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int n;
System.out.print(" => ");
n=sc.nextInt();
System.out.println("\t ");
int key[]=new int[n];
Random rn=new Random();
for (int i = 0; i < key.length;i++) {
key[i]=rn.nextInt(100);
System.out.print(key[i] + ); }
System.out.println("\n ");
int lev, prav, k;
boolean naideno;
do{
int arg,num;
System.out.println("\n ");
arg=sc.nextInt();
if (arg>=0){
num=-1;
if arg==key[n-1] {
k=n-1;
naideno=true; }
else {
naideno=false;
do {
k=(int)((lev+prav)/2);
if (arg==key[k])
naideno=true;
else
if (arg>key[k])
lev= k;
else
prav= k;
} while (!naideno || (lev==prav-1));
}
if (naideno)
System.out.println(" , "+ k);
else
System.out.println(" ");
} while (arg>=0);
}
2.2.
