65. Median of two Sorted Arrays

隐形的二分法：

Code(Language:C++) (Judger:cloudjudge-cluster-5)

class Solution {
public:
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
        // write your code here
        //核心点1是转化为找k-th smallest number; 2是能发现 比较A[k/2 - 1]和B[k/2 - 1], k th number在较小值所在的vector和 the other one中。
        //坑点: 注意index的选取，以一个简单例子看，会避免出错。
        const int m = A.size(); 
        const int n = B.size(); 
        int size = m + n; 
        if(size == 0){
            return -1; 
        }
        if(size % 2){
            return findkth(A, B, 0, 0, (size + 1) / 2);  
        }
        else{
            return (findkth(A, B, 0, 0, size / 2) + findkth(A, B, 0, 0, size / 2 + 1)) / 2.0; 
        }
    }
    
    int findkth(vector<int> &A, vector<int> &B, int sA, int sB, int k){
        // corner cases 
        if(sA >= A.size()){
            return B[sB + k - 1]; 
        }
        if(sB >= B.size()){
            return A[sA + k - 1]; 
        }
        if(k == 1){
            return min(A[sA], B[sB]); 
        }
        // decide to select which vector 
        int vA = INT_MAX, vB = INT_MAX; 
        if(sA + k/2 - 1 < A.size()){
            vA = A[sA + k/2 - 1]; 
        }
        if(sB + k/2 - 1 < B.size()){
            vB = B[sB + k/2 - 1]; 
        }
        if(vA < vB){ //
            return findkth(A, B, sA + k/2, sB, k - k/2); // remove the number of k / 2 smaller ones  
        }
        else{
            return findkth(A, B, sA, sB + k/2, k - k / 2); 
        }
        
        
    }
};