二分法查找c语言_二分法查找_二分法查找算法(5)

class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
    if((m+n) %2 == 1){
        return findMedian(A, m, B, n, (m+n)/ 2 + 1);
    }else{
        return (findMedian(A, m, B, n, (m+n)/2) + findMedian(A, m, B, n, (m+n)/2 + 1))/2.0;
    }
}
private:
  double findMedian(int A[], int m, int B[], int n, int k){
    assert(A&&B);
    if(m <= 0) return B[k-1];
    if(n <= 0) return A[k-1];
    if(k == 1) return min(A[0], B[0]);
    if(B[n/2] >= A[m/2]){
        if((m/2 + n/2 + 1) >= k)
            return findMedian(A, m, B, n/2, k);
        else
            return findMedian(A + m/2 + 1, m - (m/2 + 1), B, n, k - m/2 -1);
    }else{
        if((m/2 + n/2 + 1) >= k)
            return  findMedian(A, m/2, B, n, k);
        else
           return findMedian(A, m, B + n/2 + 1, n - (n/2 + 1), k - n/2 - 1);

      }
    }
 };

这道题还有更简洁的方法，即确保A数组的个数永远不大于B数组的个数，如果不是就交换这两个数组。二分法查找

   class Solution {
     public:
   double findMedianSortedArrays(int A[], int m, int B[], int n) {
    int total = m + n;
    if( total & 0x1 ){
        return findMedian(A, m, B, n, total/2 + 1);
    }else{
        return (findMedian(A, m, B, n, total/2) + findMedian(A, m, B, n, total/2 + 1))/2.0;
    }
}
  private:
   int findMedian(int A[], int m, int B[], int n, int k){
    if(m > n) return findMedian(B, n, A, m, k);
    if(m == 0) return B[k-1];
    if(k == 1) return min(A[0], B[0]);

    int ia = min(k/2, m), ib = k - ia;
    if(A[ia-1] < B[ib-1])
        return findMedian(A + ia, m -ia, B, n, k -ia);
    else if(A[ia - 1] > B[ib - 1])
        return findMedian(A, m, B +ib, n -ib, k -ib);
    else
        return A[ia - 1];
       }
  };

例题： Search a 2D matrix

复杂度： 时间O(log (m*n)), 空间O(1).

分析：首先这道题中二维数组有两个特点：

每一行数是递增的

每一行第一个数都小于上一行的最后一个数

因此很自然的想到把二维数组压平为一位数组，然后使用binary search解决。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26574-5.html