NC36—在兩個長度相等的排序數組中找到上中位數

題意

給定兩個有序數組

arr1

和

arr2

，已知兩個數組的長度都為

N

，求兩個數組中所有數的上中位數

上中位數：假設遞增序列長度為

n

，若

n

為奇數，則上中位數為第

n/2+1

個數，否則為第

n/2

個數

[要求]

時間複雜度為 O ( l o g N ) O(logN) O(logN)，額外空間複雜度為 O ( 1 ) O(1) O(1)

題解

要求時間複雜度為 O ( l o g N ) O(logN) O(logN)，很容易想到二分查找，關鍵是怎麼二分

1. 如果每個數組中隻有一個元素，較小的那個元素就是整體的上中位數，如果兩個元素相等，随便傳回哪個都可以。
2. 如果數組中不止一個元素，找到兩個數組的中間位置mid1和mid2。
3. 如果arr1[mid1] == arr2[mid2]，不管每個數組中元素的個數是奇數還是偶數，這兩個數都可以是整體的上中位數，傳回其中一個就可以。
4. 如果arr1[mid1] > arr2[mid2]，每個數組的個數是奇數的情況下：數組arr1中mid1位置以後的數都不可能是整體的上中位數，數組arr2中mid2位置以前的數都不可能是整體的上中位數。是以現在隻需要考慮arr1[left1…mid1]、arr2[mid2…right]，這兩部分的元素個數相同，它們的上中位數就是整體的上中位數。
5. 如果arr1[mid1] > arr2[mid2]，每個數組的個數是偶數的情況下：數組arr1中mid1位置以後的數都不可能是整體的上中位數，數組arr2中mid2位置以後包括mid2位置，都不可能是整體的上中位數。是以現在隻需要考慮arr1[left1…mid1]、arr2[mid2+1…right]，這兩部分的元素個數相同，它們的上中位數就是整體的上中位數。
6. arr1[mid1] < arr2[mid2]的情況，分析同上。

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int end1 = arr1.size()-1;
        int end2 = arr2.size()-1;
        int start1 = 0, start2 = 0;
        int mid1, mid2;
        while(start1 < end1){
            mid1 = (start1 + end1)/2;
            mid2 = (start2 + end2)/2;
            // 如果有序數組是偶數，偏移量為1，否則為0
            int offset = (end1-start1+1)&1^1;
            if(arr1[mid1] == arr2[mid2]){
                return arr1[mid1];
            }
            else if(arr1[mid1] < arr2[mid2]){
                start1 = mid1 + offset;
                end2 = mid2;
            }
            else{
                end1 = mid1;
                start2 = mid2 + offset;
            }
        }
        return min(arr1[start1], arr2[start2]);
    }
};