#include <iostream>
#include <string>
using namespace std;
int main(int argc,char* argv[])
{
int A[]={1,3,5,7,8,9};
int B[]={2,4,6,10,11,12,13,14};
int sizeA = sizeof(A)/sizeof(int);
int sizeB = sizeof(B)/sizeof(int);
int ma=0,na=sizeA-1;
int mb=0,nb=sizeB-1;
while(1)
{
int ka=(na+ma+1)/2;
int kb=(nb+mb+1)/2;
if(na<ma)
{
cout<<B[kb]<<endl;
break;
}
if(nb<mb)
{
cout<<A[ka]<<endl;
break;
}
if(A[ka]==B[kb])//find the value
{
cout<<A[ka]<<endl;
break;
}
if((ma==na)&&((nb-mb+1)%2==0))//there is only one element at A[]
{
if((A[na]<B[kb])&&(A[na]>=B[kb-1]))
{
cout<<A[na]<<endl;
break;
}
}
if((ma==na)&&((nb-mb+1)%2))
{
if((A[na]>B[kb])&&(A[na]<=B[kb+1]))
{
cout<<A[na]<<endl;
break;
}
}
if((mb==nb)&&((na-ma+1)%2==0))//there is only one element at B[]
{
if((B[nb]<A[ka])&&(B[nb]>=A[ka-1]))
{
cout<<B[nb]<<endl;
break;
}
}
if((mb==nb)&&((na-ma+1)%2))
{
if((B[nb]>A[ka])&&(B[nb]<=A[ka+1]))
{
cout<<B[nb]<<endl;
break;
}
}
int offset=ka-ma;
if(offset>(kb-mb))
offset=kb-mb;
if(offset==0)
offset++;
//int offset=((ka>=kb)?ka:kb);
if(A[ka]<B[kb])
{
ma+=offset;
nb-=offset;
}
if(A[ka]>B[kb])
{
na-=offset;
mb+=offset;
}
}
system("pause");
return 0;
}