一道笔试题（创新工厂）

由于a,b数组都是有序的。而且a.length<b.length
可以先从b中用二分法找出a[0]与a[a.length-1]这两个数在b中对应的下标。
即
b[0]<=b[1]<=....<=b[i]<=a[0]<=a[1]<=....<=a[a.length-1]<=b[j]<=b[b.length-1]

这样在对b进行遍历时没必要从开头循环还结尾。只需要从b[i]循环到b[j]就行了。

例如
a[]={10,11,12}
b[]={1,2,3,4,5,6,7,8,9,10,10,11,13,13}
对于b只需要循环{10,10,11}子数组就行了，没必须循环{1,2,3,4,5,6,7,8,9,10,10,11,13,13}

另外对于内外循环。
for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
     ...
    }
}
也是没有必要的。
因为你要找a[0]时发现它在b中的下标是x。那么找a[1]在b中位置是没必要从b[0]开始，应该从b[x+1]开始，假设位置为y，则a[2]在b中的位置应该人b[y+1]开始。

大概代码是这样的
int blow=从b[0,blen-1]中二分搜索a[0]，直到遇到b[j]=a[0]或b[j+1]>a[0]或b[j-1]<a[0]结束
int bhign=从b[blow+1,blen-1]中二分二分搜索a[alen-1]，直到遇到b[k]=a[alen-1]或b[k+1]>a[alen-1]或b[k-1]<a[alen-1]结束

var bNowIndex=0;
for(int i=0;i<alen;i++){
        for(;bNowIndex<blen;){
                if(b[bNowIndex]=a[i]){
                        System.out.println(a[i]);
                        bNowIndex++;
                        break;
                }else{
                        bNowIndex++;
                }
        }
}


时间复杂度为
log2(blen)+log2(blen-blow)+(bhign-blow)
平均时间复杂度为2log2(blen)-3+blen/4

这是一个改进的binarysearch，因为a中的元素b不一定存在
下一步继续从左到右二元搜索，每一次搜索都进行边界修正

        set<int>s1,s2;
int array_A[10]={1,4,6,8,5,3,5,4,4,9};
int array_B[25]={2,4,5,6,7,44,9,45,3,3,2,4,45,6,7,7,5,3,4,4,5,7,7};
set<int>::iterator posA;
set<int>::iterator posB;
for (int i=0;i<10;++i)
{
s1.insert(array_A[i]);
}
for (int i=0;i<23;++i)
{
s2.insert(array_B[i]);
}
posA=s1.begin();
while (posA!=s1.end())
{
posB=s2.lower_bound(*posA);
if (*posB==*posA)
{
cout<<*posA<<endl;
s2.erase(s2.begin(),posB);
++posA;
}
else
{
++posA;
while (posA!=s1.end())
{
if (*posA==*posB)
{
cout<<*posA<<endl;
s2.erase(s2.begin(),posB);
++posA;
break;
}
else if(*posA>*posB)
{
s2.erase(s2.begin(),posB);
break;
}
++posA;
}
}
}

在vc中我是这样写的，不知道，时间复杂度有没有更精简，希望大家参考