題目連結：
力扣

題目描述

給定兩個大小分別為 m 和 n 的正序（從小到大）陣列 nums1 和 nums2。
請你找出並返回這兩個正序陣列的 中位數 。演算法的時間複雜度應該為 O(log (m+n))

題目分析

常規思路：
1.合併兩個陣列再排序，時間複雜度O(m+n)，空間複雜度O(m+n)
2.歸併排序，時間複雜度O(m+n)，空間複雜度O(1)
本題解題思路應該如何呢？

根據題目中時間複雜度，可以考慮採用二分查詢，這也是本題的難度所在。

假設兩個有序陣列分別是 A 和 B，兩陣列的總長度為 totalLength：

• 兩陣列總長度（totalLength）為奇數：中位數下標(midIndex)=totalLength/2，中位數=下標midIndex所在數；
• 兩陣列總長度（totalLength）為偶數，中位數下標有兩個 midIndex1，midIndex2， midIndex1=totalLength/2-1 ，midIndex2=totalLength/2，中位數=(下標midIndex1所在數+下標midIndex2所在數)/2；

注意：midIndex，為兩數組合並後的下標，並不是真的將兩個陣列進行合併，大家要搞清楚這個概念。

這個時候，問題轉化為找到陣列 A 和 B 中的第 k 大元素（kElement），那怎麼找到呢？
可以比較 A[k/2-1] 與B[k/2-1] ：

• A[k/2−1]<=B[k/2−1]，則陣列A中，下標為 0 至 k/2−1 的元素均小於kElement，可以排除這部分元素；
• A[k/2−1]>B[k/2−1]，則陣列B中，下標為 0 至 k/2−1 的元素均小於kElement，可以排除這部分元素；

很容易想到，查詢範圍縮小了一半，可以在排除後的新陣列上繼續進行二分查詢，並且根據我們排除數的個數，減少 k 的值（因為我們排除的數都不大於第k 小的數）。需要注意以下幾種情況：

1.保證陣列不越界；

2.如果一個數組為空，說明該陣列中的所有元素都被排除，我們可以直接返回另一個數組中第k小的元素；

3.若 k=1，只要返回兩個陣列首元素的最小值即可。

程式碼實現

• 時間複雜度：O(log (m+n))
• 空間複雜度：O(1)

public class FindMedianSortedArrays_4 {

    /**
     * 常規思路：
     * 《1》合併兩個陣列在排序
     * 《2》歸併排序
     *
     * @param args
     */

    public static void main(String[] args) {
        int[] num1 = {1, 3};
        int[] num2 = {2};
        //int[] num1 = {1, 3,4,9};
        //int[] num2 = {1,2,3,4,5,6,7,8,9};
        FindMedianSortedArrays_4 findMedianSortedArrays_4 = new FindMedianSortedArrays_4();
        findMedianSortedArrays_4.findMedianSortedArrays(num1, num2);

    }

    /**
     * 二分查詢，巧妙
     * 時間複雜度：O(log (m+n))
     * 空間複雜度：O(1)
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLength = length1 + length2;

        // 兩陣列總長度（totalLength）為奇數，中位數下標(midIndex)=totalLength/2，中位數=下標k所在數
        if (totalLength % 2 == 1) {
            System.out.println("兩陣列總長度（totalLength）為奇數");
            int midIndex = totalLength / 2;

            double median = getKthElement(nums1, nums2, midIndex + 1);
            System.out.println("median:" + median);
            return median;

        } else {
            // 兩陣列總長度（totalLength）為偶數，中位數下標有兩個 midIndex1，midIndex2， midIndex1=totalLength/2-1 ，midIndex2=totalLength/2，
            // 中位數=(下標midIndex1所在數+下標midIndex2所在數)/2
            System.out.println("兩陣列總長度（totalLength）為偶數");

            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            System.out.println("median:" + median);

            return median;

        }
    }

    /**
     * 獲取第k小的元素
     *
     * @param nums1
     * @param nums2
     * @param k
     * @return
     */
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        System.out.println("初始k:" + k);

        int length1 = nums1.length;
        int length2 = nums2.length;

        // 用來記錄兩個陣列尋找第k小元素的起始下標
        int index1 = 0, index2 = 0;

        while (true) {
            // 邊界情況，陣列1為空，只需要考慮陣列2
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            // 邊界情況，陣列2為空，只需要考慮陣列1
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // 比較 num1[k/2-1] 與 num1[k/2-1]
            int compareIndex1 = Math.min(index1 + k / 2, length1) - 1;
            int compare1 = nums1[compareIndex1];
            int compareIndex2 = Math.min(index2 + k / 2, length2) - 1;
            int compare2 = nums2[compareIndex2];

            if (compare1 < compare2) {

                k -= compareIndex1 - index1 + 1;

                index1 = compareIndex1 + 1;

            } else {
                k -= compareIndex2 - index2 + 1;
                index2 = compareIndex2 + 1;

            }
            System.out.println("compare1:" + compare1);
            System.out.println("compare2:" + compare2);
            System.out.println("index1:" + index1);
            System.out.println("index2:" + index2);
            System.out.println("k:" + k);

        }

    }

}

注意：while語句中是最核心的部分，也就是二分查詢的主要思想。