. , a. .
1 ( ). , , . . . , , : . : 1) ; 2) , . .
, : i >= n, i - , n - .
: , , true , false - .
, (i>=n-1) || f, : . . , : .
!((i>=n) || f) = =!(i>=n) &&! f = = (i<n) &&! f.
//
const int nn=12; //
int []b=new int b[nn];//
int n; //
int a; //
int i; //
bool f; //,
i=0; //
f=false; //
while ((i<n) &&! f)
// ,
if (b[i]= =a) // ,
f=true // ,
else i++; //
if f //
Console.WriteLine( +i);
else Console.WriteLine( );
.
1. n=8, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=2, B[6]=2, B[7]=2, a=5. : .
2. n=7, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=8, B[6]=2, a=8. : 1.
2 ( ). , , . , .. , , , .
//
|
|
const int nn=12; //
int []b=new int b[nn];//
int n; //
int a; //
int i; //
bool f; //,
b[n+1]=a; // , ,
i=0; //
while (b[i]!=a) i++
// ,
if (i<n) //
Console.WriteLine( +i);
else Console.WriteLine( );
.
1. n=8, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=2, B[6]=2, B[7]=2, a=5. : .
2. n=7, B[0]=2, B[1]=8, B[2]=3, B[3]=1, B[4]=9, B[5]=8, B[6]=2, a=8. : 1.
:
1. .
2. , .
3 ( , ). , () . . , . , , , . , , . , , . . , . , , . ]log2N[, N - .
.
a=7. n=16.
:
: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15;
B={ 1, 3, 5, 6, 7,10,12,14,15,16,20,21,23,25,26,30 };
L=0, R=15;
i=(L+R) / 2 = 7;
B[7]=14>a=7, : L=0, R=i-1=6.
:
: 0 1 2 3 4 5 6;
B={ 1, 3, 5, 6, 7,10,12 };
L=0, R=6;
i=(L+R)/ 2 = 3;
B[3]=6<a=7, : L=i+1=4, R=6.
:
: 4 5 6;
B={ 7,10,12 };
L=4, R=6;
i=(L+R) / 2 = 5;
B[5]=10>a=7, : L=4, R=i-1=4.
:
: 4;
B={ 7 };
L=4, R=4;
i=(L+R)/ 2 = 4;
B[5]=7= =a=7, 5.
, , :
l=0; r=n-1;
f=false; //
while((l<=r) &&! f)
{ i=(l+r) / 2;
if (b[i]= =a) f=true; //
else if (b[i]<a) l=i+1; else r=i-1;
}
.
|
|
1: a=7, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
: 3.
2: a=6, n=15, b={1,3,5,7,9,10,12,14,16,18,21,23,25,27,29}.
: .