二分查找-- More

2015-08-26

@(笔试面试)

二分查找在笔试面试中泰常见，比如我在某夹公司实习面试的时候题目，总结写在实习面试三，还有另外一篇关于二分查找上下界，今天又遇到一个比较难的问题,还是关于二分查找,开始自己的思路并不是很明确,有个大概的想法,还不知道具体实施方式,参考了别人的解析,终于有些思路,把自己的想法和思路总结一下.

原始题目:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

也就是LeetCode的004号题目,定义难度级别是hard.通俗的理解就是求解两个有序数组中位数,若是偶数个,就求两个中位数的平均值.

我最开始的思路是两个指针分别遍历,向中间走,但是题目明确要求使用二分查找,不知道到底这个二分从哪里下手.

还是参考别人的想法吧

之前学习的二分查找的对象是一个有序数组,但是这里是两个有序数组,How?
把两个数组也看做是一个数组,分成两部分:左半部分和右半部分:

1 2	nums1:{0,1,2,...,i-1} + {i,i+1,...,len1-1}; nums2:{0,i,2,...,j-1} + {j,j+1,...,len2-1};

正如上面的伪代码标识,两个数组分别用两个标志i和j将两个数组分割开,两个数组的左半部分构成整体的左半部分,两个数组的右半部分构成了整体的右半部分:

Left Part:
nums1: {0,1,2,...,i-1} ;
nums2: {0,i,2,...,j-1} ;

Right Part:
nums1: {i,i+1,...,len1-1} ;
nums2: {j,j+1,...,len2-1} ;

但是这里有两个变量,二分查找只有一个变量,How?

二分查找单个数组的中位数,就是找一个点,使得这个点满足:左边数字的个数 == 右边数字的个数,并且,左边的数字 <= 右边的数组.
对于两个数组,其实也是要找到这样的分割点,这里的分割点是两个,因为这里要将两个数组分割组成整体的左右两部分,也就是上面的i和j,使得整体左边的数字的个数 == 整体右边数字的个数,并且,整体左边的数字 <= 整体右边的数字.
不同的是,单个数组可以直接计算得到,两个数组寻找这个点的过程麻烦一点,因为有两个分割点.

两个分割点不好求,那就转换成求解一个分割点,另外一个分割点与之关联,也就得到了,How?
通过上面的两个条件:

整体左边的数字的个数 == 整体右边的数字的个数: 也就是(i+j) == (len1-i) +(len2-j),或者总数是奇数的时候:(i+j) == (len1-i) +(len2-j)+1,这样可以用i标识j:j=(m+n+1)/2 - i;这样就转换成一个变量i了.
整体左边的数字 <= 整体右边的数字:即如下:
1
2
nums1[i-1] < nums2[j];
nums2[j-1] < nums2[i];

与单个数组不同,单个数组只需要一个计算就可以了,这里需要不断的调整分割点i来满足条件.这个调整i的过程就是利用单个数组二分查找的过程,这样的操作复杂度才能是O(logN).怎样调整i?

这里我们设定i是自变量,那么就设定nums1的长度len1 <= len2.这里的证明不太好说,直白点说,若是len2<= len1再调整i的过程中可能导致j越界.

设定i的二分查找范围,最开始的时候范围是[0,len1],当i==0 的时候,表示数组nums1全部在右边,数组nums2全部在左边,当i==len1的时候,数组nums1全部在左边,数组nums1全部在右边.
循环调整(二分调整):while(min_i <= max_i)
若满足 i>0 && j nums2[j],这时候数组nums1的左半部分的数字存在大于数组nums2右半部分的数字,需要将i减小,以上判断是在满足两个分界点都不越界的情况的.
若满足 j>0 && i nums1[i],这时候数组nums2的左半部分的数字存在大于数组nums1右半部分的数字,需要将j减小,也就是要让i变大.以上判断是在满足两个分界点都不越界的情况的.
正常结束:min_i > max_i,此时的i就是正确的分界点,同时也能得到数组nums2的分界点.若总数是奇数个,那么返回max(nums1[i-1],nums2[j-1])(因为左半部分要比右半部分多一个).若是总数是偶数个,那么就要求左半部分的最大值,与又半部分最小值的平均值.
越界结束:若i==0说明左边的最大值是在数组2nums2的[j-1]位置,若j==0说明左边的最大值是在数组1nums1的[i-1]位置.若是总数是奇数,则返回这个左侧的最大值就可以了.
若是偶数,还要求右侧的最小值,若i==len1,则右侧最小值是nums2[j],若是j==len2,则右侧的最小值是nums1[i],若没有越界,则右侧最小值是min(nums1[i],nums2[j])

不是很好理解,下面是代码实现

int len1,len2;
    len1 = nums1.size();
    len2 = nums2.size();
    if(len1 > len2)
        return findMedianSortedArrays(nums2,nums1);
    int i,j;
    int mid;
    int min_i,max_i;
    int n1,n2;
    min_i = 0;
    max_i = len1;
    mid = (len1 + len2 + 1) / 2;
    while(min_i <= max_i)
    {
        i = (min_i + max_i) / 2;
        j = mid - i;
        if(i >0 && j<len2 && nums1[i-1] > nums2[j])
            max_i = i -1;
        else if(j>0 && i<len1 && nums2[j-1] > nums1[i])
            min_i = i + 1;
        else
            break;
    }

    if(i == 0)
        n1 = nums2[j-1];
    else if(j==0)
        n1 = nums1[i-1];
    else
        n1 = max(nums1[i-1],nums2[j-1]);

    if((len1 + len2) & 1)
        return n1;
    if(i == len1)
        n2 = nums2[j];
    else if(j == len2)
        n2 = nums1[i];
    else
        n2 = min(nums1[i],nums2[j]);
    return (n1 + n2) / 2.0;

参考

LeetCode讨论