算法-两个有序数组找交集

有两个长度分别为m,n的升序数组,其中n> m*m,求这两个数组的交集,要求其复杂度尽可能低。
如：数组a :-10,6,7
数组b:-15,1,3,4,5,6,7,8,9,10,15
输出：6，7

时间复杂度对比曲线.png

思路分析：最直接的思路，两层循环嵌套，找出两者的交集。

void intersection0(int *a,int lenA,int *b,int lenB)
{
    for (int i = 0 ; i < lenA; i ++) {
         int num = *(a + i);
        for (int j = index ; j < lenB; j ++) {
            int temp = *(b + j);
            if (num == temp) {
                printf("%d ",num);
            }
        }
    }
}

时间复杂度分析：
最好的情况为：m + （1 + 2 + ... + m = m + m^2 /2+m/2 渐进为m^2 ;
最坏的情况为：m + m *(m *m) = m^3 +m ；渐进为m^3；
平均复杂度为：m^3

优化：
由于本身是一个升序的数列，当第一个元素查找到的时候，其下标为index，那么把index+1作为下一个元素的查找起始下标；如果第一个元素没有找到，记录B数组第一个比他大的元素的index作为下一个元素的查找起始下标。通过把查找范围不断缩小，查找的效率就会有所提高。优化后的代码：

void intersection0(int *a,int lenA,int *b,int lenB)
{
    for (int i = 0 ; i < lenA; i ++) {
        int num = *(a + i);
        int index = 0;
        for (int j = index ; j < lenB; j ++) {
            int temp = *(b + j);
            if (num == temp) {
                index = j + 1;//记录下标，作为下一元素的起始查找下标。
                printf("%d ",num);
            }
            else if (temp > num)
            {
                index = j;//记录下标，作为下一元素的起始查找下标。
            }
        }
    }
}

优化后的时间复杂度分析：
最好的情况为：m + m = 2m 渐进为m；
最坏的情况为：m + 1 + 2+ 3...+ m 渐进为 m^2 ；
平均时间复杂度为：m^2

//另外一种写法,时间复杂度跟上面的一样
void intersection1(int *a,int len0,int *b,int len1)
{
    int i ,j;
    i = 0;
    j = 0;
    while (i <= len0 - 1 && j <= len1 - 1) {
        if (*(a + i) == *(b + j)) {
            i ++;
            j ++;
        }
        else if (*(a + i) > *(b + j))
        {
            j ++;
        }
        else
        {
            i ++;
        }
    }
}

分析与改进

可见上面的算法都是m的平方阶或立方阶，并不理想。因为a数组遍历是必须的，问题就转变为提高在b数组中查找效率。复杂度计算应该为m(??)这样的形式，可不可以实现m(logm)这样的线性对数阶呢。答案是可以的，使用二分查找就能实现。同时为了在查找的过程中不断收窄比较范围，使用双向间隔查找的方式。

具体过程如下：
先查找a[0]并收窄查找下限，然后查找a[lenA - 1- 0]并收窄查找上限，然后进入下一轮。另外b数组的元素分布比较均匀的话，可以使用插值查找，效率会比二分法高不少。插值查找关键步骤mid = low + (height - low ) *(key - b[low])/(b[height]-b[low] )。

void intersection(int *a,int len0,int *b,int len1)
{
    int low = 0;
    int height = len1 - 1;
    
    int tempLow = low;
    int tempHeight = height;
    
    int mid;
    
    //双向间隔遍历查找
    for (int i = 0 ; i <= len0/2; i ++) {
        
        //如果是同于个元素结束,考虑i执行了++，就是上轮的右边等于当前的左边
        if(i == len0  - i)
        {
            break;
        }
        
        low = tempLow;
        height = tempHeight;
        mid = (low + height)/2;
        //左边开始查找,并调整下限
        int  num = *(a + i);
        while (height >= low) {
             printf("mid %d\n",mid);
            int temp = *(b + mid);
            if (num == temp) {
                tempLow = mid;//调整下限
                break;
            }
            else if (low == height)
            {
                tempLow = mid;//调整下限
                break;
            }
            else if (num < temp)
            {
                height = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
            mid = (low + height)/2;
        }
        
        printf("-------右边-----\n");
        //如果是同于个元素结束
        if(i == len0 - 1 - i)
        {
            break;
        }
        
        low = tempLow;
        height = tempHeight;
        mid = (low + height)/2;
        //右边开始查找,并调整上限
        int  num1 = *(a + len0 - 1 - i);
        while (height >=low) {
            int temp = *(b + mid);
            if (num1 == temp) {
                tempHeight = mid;//调整上限
                break;
            }
            else if (low == height)
            {
                tempHeight = mid;//调整上限
                break;
            }
            else if (num1 < temp)
            {
                height = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
            mid = (low + height)/2;
        }
    }
}

但是，这样输出的顺序也是间隔的。所以，如果要求输出是升序的话，这个输出的时候就要处理下，左边遍历的可以马上输出，右边遍历的需要存储起来，处理结束后，再顺序输出。

参考资料：
插值查找:
https://blog.csdn.net/wangyunyun00/article/details/23464359