原文：Median of two sorted arrays

题目：两个有序数组A和B，大小都是n，寻找这两个数组合并后的中位数。时间复杂度为O(logn)。
中位数：如果数组有个数是奇数，那么中数的值就是有序时处于中间的数；如果数组个数是偶数的，那么就是有序时中间两个数的平均值。

方法一：合并时计数
使用Merge Sort时的Merge操作，比较两个数组时候计数，当计数达到n时，就可以得到中位数，在归并的数组中，中位数为下标n-1和n的两个数的平均值。
时间复杂度O(n)。

#include   

//

1. This function returns median of ar1[] and ar2[].     
2. Assumptions in this function:     
3. Both ar1[] and ar2[] are sorted arrays     
4. Both have n elements//

int getMedian(int ar1[], int ar2[], int n)
{
    int i = 0;     //Current index of i/p array ar1[]
    int j = 0;    //Current index of i/p array ar2[]
    int count;    
    int m1 = -1, m2 = -1;     
 
    //

1.  Since there are 2n elements, median will be average of elements at index n-1 and n  
2.     in the array obtained after merging ar1 and ar2
   

    for (count = 0; count <= n; count++)    
    {        
               
        if (i == n)        
        {            
            m1 = m2;            
            m2 = ar2[0];          
            break;      
        }        
               
        else if (j == n)        
        {   
            m1 = m2; 
            m2 = ar1[0]; 
            break;       
        }       
        if (ar1[i] < ar2[j])   
        { 
            m1 = m2;             
            m2 = ar1[i];            
            i++;       
        }       
        else      
        {         
            m1 = m2;           
            m2 = ar2[j];         
            j++;      
        }   
    }     
    return (m1 + m2)/2;
}  


int main()
{   
    int ar1[] = {1, 12, 15, 26, 38};    
    int ar2[] = {2, 13, 17, 30, 45};     
    int n1 = sizeof(ar1)/sizeof(ar1[0]);   
    int n2 = sizeof(ar2)/sizeof(ar2[0]);   
    if (n1 == n2)      
        printf("Median is %d", getMedian(ar1, ar2, n1));   
    else      
        printf("Doesn't work for arrays of unequal size"); 

    return 0;
}

方法二：比较两个数组的中位数

ar1[]和ar2[]为输入的数组
算法过程：
1.得到数组ar1和ar2的中位数m1和m2
2.如果m1==m2，则完成，返回m1或者m2
3.如果m1>m2，则中位数在下面两个子数组中
   a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
   b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4.如果m1
   a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5.重复上面的过程，直到两个子数组的大小都变成2
6.如果两个子数组的大小都变成2，使用下面的式子得到中位数
   Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

时间复杂度：O(logn)。

#include   


int max(int x, int y)
{    
    return x > y? x : y;
} 

int min(int x, int y)
{  
    return x > y? y : x;
}


int median(int arr[], int n)
{  
    if (n%2 == 0)      
        return (arr[n/2] + arr[n/2-1])/2;   
    else     
        return arr[n/2];
} 


int getMedian(int ar1[], int ar2[], int n)
{
    int m1;  
    int m2;    

   
    if (n <= 0)      
        return -1;   
    if (n == 1)     
        return (ar1[0] + ar2[0])/2;   
    if (n == 2)     
        return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2; 

    m1 = median(ar1, n);  
    m2 = median(ar2, n);
     
       
    if (m1 == m2)      
        return m1;      

     
    if (m1 < m2) 
    {      
        if (n % 2 == 0)         
            return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);     
        else     
            return getMedian(ar1 + n/2, ar2, n - n/2);  
    }     

       
    else  
    {   
        if (n % 2 == 0)       
            return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);       
        else         
            return getMedian(ar2 + n/2, ar1, n - n/2);   
    }
}


int main()
{   
    int ar1[] = {1, 2, 3, 6}; 
    int ar2[] = {4, 6, 8, 10}; 
    int n1 = sizeof(ar1)/sizeof(ar1[0]); 
    int n2 = sizeof(ar2)/sizeof(ar2[0]);   
    if (n1 == n2)   
        printf("Median is %d", getMedian(ar1, ar2, n1));  
    else   
        printf("Doesn't work for arrays of unequal size");  

    return 0;
}

方法三：通过二分查找法来找中位数

基本思想是：假设ar1[i]是合并后的中位数，那么ar1[i]大于ar1[]中前i-1个数，且大于ar2[]中前j=n-i-1个数。通过 ar1[i]和ar2[j]、ar2[j+1]两个数的比较，在ar1[i]的左边或者ar1[i]右边继续进行二分查找。对于两个数组 ar1[] 和ar2[], 先在 ar1[] 中做二分查找。如果在ar1[]中没找到中位数, 继续在ar2[]中查找。

算法流程：
1) 得到数组ar1[]最中间的数，假设下标为i.
2) 计算对应在数组ar2[]的下标j，j = n-i-1
3) 如果 ar1[i] >= ar2[j] and ar1[i] <= ar2[j+1]，那么 ar1[i] 和 ar2[j] 就是两个中间元素，返回ar2[j] 和 ar1[i] 的平均值
4) 如果 ar1[i] 大于 ar2[j] 和 ar2[j+1] 那么在ar1[i]的左部分做二分查找(i.e., arr[left ... i-1])
5) 如果 ar1[i] 小于 ar2[j] 和 ar2[j+1] 那么在ar1[i]的右部分做二分查找(i.e., arr[i+1....right])
6) 如果到达数组ar1[]的边界(left or right)，则在数组ar2[]中做二分查找

时间复杂度：O(logn)。

#include   


int getMedianRec(int ar1[], int ar2[], int left, int right, int n)
{   
    int i, j;

     
    if(left > right)     
        return getMedianRec(ar2, ar1, 0, n-1, n); 

    i = (left + right)/2;   
    j = n - i - 1;     

      
    if (ar1[i] > ar2[j] && (j == n-1 || ar1[i] <= ar2[j+1]))  
    {     
          
        if (ar2[j] > ar1[i-1] || i == 0)       
            return (ar1[i] + ar2[j])/2;     
        else         
            return (ar1[i] + ar1[i-1])/2; 
    }

      
    else if (ar1[i] > ar2[j] && j != n-1 && ar1[i] > ar2[j+1])    
        return getMedianRec(ar1, ar2, left, i-1, n);  

       
    else  
        return getMedianRec(ar1, ar2, i+1, right, n);
}


int getMedian(int ar1[], int ar2[], int n)
{  
    // If all elements of array 1 are smaller then 
    // median is average of last element of ar1 and first element of ar2  
    if (ar1[n-1] < ar2[0])   
        return (ar1[n-1]+ar2[0])/2;    

    // If all elements of array 1 are smaller then   
    // median is average of first element of ar1 and   
    // last element of ar2  
    if (ar2[n-1] < ar1[0])   
        return (ar2[n-1]+ar1[0])/2; 
 
    return getMedianRec(ar1, ar2, 0, n-1, n);
}
 

{  
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45}; 
    int n1 = sizeof(ar1)/sizeof(ar1[0]);  
    int n2 = sizeof(ar2)/sizeof(ar2[0]);  
    if (n1 == n2)     
        printf("Median is %d", getMedian(ar1, ar2, n1));   
    else    
        printf("Doesn't work for arrays of unequal size"); 

    return 0;
}

原文地址：http://www.geeksforgeeks.org/archives/2105

http://blog.csdn.net/luxiaoxun/article/details/7960353