有两个长度分别为m,n的升序数组,其中n> m*m,求这两个数组的交集,要求其复杂度尽可能低。
如：数组a :-10,6,7
数组b:-15,1,3,4,5,6,7,8,9,10,15
输出：6，7
思路分析：最直接的思路，两层循环嵌套，找出两者的交集。
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
