LeetCode 4：尋找兩個正序數組的中位數

問題定義與核心挑戰

給定兩個有序（升序）數組 nums1 和 nums2，要求找到它們的中位數，且算法時間復雜度為 O(log(m+n))（m 和 n 分別是兩個數組的長度）。

中位數定義：

• 若合并后數組長度為奇數，中位數是中間位置的元素（如 [1,2,3] 的中位數是 2）。
• 若合并后數組長度為偶數，中位數是中間兩個元素的平均值（如 [1,2,3,4] 的中位數是 (2+3)/2=2.5）。

常規方法的不足

若直接合并兩個數組（時間復雜度 O(m+n)），雖能解決問題，但無法滿足題目對時間復雜度的嚴格要求（O(log(m+n))）。因此，必須利用數組有序的特性，通過 二分查找 避免完全合并。

核心思路：二分法定位分割點

中位數的本質是將合并后的數組劃分為左右兩部分，使得：

• 左邊所有元素 ≤ 右邊所有元素；
• 左邊元素個數 ≥ 右邊（奇數長度時左邊多一個）。

對于兩個有序數組，我們可以通過二分查找分割點，將 nums1 和 nums2 分別劃分為左右兩部分，使得：

• nums1 的左半部分 + nums2 的左半部分 ≤ nums1 的右半部分 + nums2 的右半部分；
• 左半部分總元素數為 (m+n+1)//2（向上取整，保證奇數長度時左邊多一個）。

算法步驟詳解

步驟 1：統一數組長度（優化二分范圍）

為了減少二分查找的范圍，確保 nums1 是較短的數組（若 nums1 更長，則交換 nums1 和 nums2）。這樣，二分查找僅需在較短數組上進行，降低時間復雜度。

int m = nums1.length, n = nums2.length;
if (m > n) {// 交換數組，確保 nums1 是較短的int[] temp = nums1;nums1 = nums2;nums2 = temp;m = nums1.length;n = nums2.length;
}

步驟 2：二分查找分割點

在 nums1 中二分查找分割點 i，并計算 nums2 的對應分割點 j：

• i 表示 nums1 左半部分的元素個數（范圍：0 ≤ i ≤ m）；
• j = (m + n + 1) // 2 - i，保證左半部分總元素數為 (m+n+1)//2（向上取整）。

int left = 0, right = m;
while (left < right) {// 向上取整，避免死循環（如 left=1, right=2 時，mid=2）int mid = (left + right + 1) / 2; int j = (m + n + 1) / 2 - mid;if (nums1[mid-1] > nums2[j]) {// i 太大，左移右邊界right = mid - 1;} else {// i 太小，右移左邊界left = mid;}
}
int i = left;
int j = (m + n + 1) / 2 - i;

步驟 3：處理邊界值（分割點越界）

分割點 i 或 j 可能為 0（左半部分為空）或等于數組長度（右半部分為空），需用極值（-∞ 或 +∞）處理：

// nums1 左半部分的最大值（i=0 時，左半部分為空，設為 -∞）
double nums1_left = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];
// nums1 右半部分的最小值（i=m 時，右半部分為空，設為 +∞）
double nums1_right = (i == m) ? Integer.MAX_VALUE : nums1[i];
// nums2 左半部分的最大值（j=0 時，左半部分為空，設為 -∞）
double nums2_left = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
// nums2 右半部分的最小值（j=n 時，右半部分為空，設為 +∞）
double nums2_right = (j == n) ? Integer.MAX_VALUE : nums2[j];

步驟 4：計算中位數

根據合并后數組的長度（m+n）的奇偶性，計算中位數：

• 奇數：左半部分最大值（max(nums1_left, nums2_left)）；
• 偶數：左半部分最大值與右半部分最小值的平均值（(max(...) + min(...)) / 2）。

if ((m + n) % 2 == 1) {// 奇數長度，中位數是左半部分最大值return Math.max(nums1_left, nums2_left);
} else {// 偶數長度，中位數是左右部分的中間值平均return (Math.max(nums1_left, nums2_left) + Math.min(nums1_right, nums2_right)) / 2.0;
}

完整代碼（Java）

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;// 確保 nums1 是較短的數組，優化二分范圍if (m > n) {int[] temp = nums1;nums1 = nums2;nums2 = temp;m = nums1.length;n = nums2.length;}int left = 0, right = m;while (left < right) {// 向上取整，避免死循環int mid = (left + right + 1) / 2; int j = (m + n + 1) / 2 - mid;if (nums1[mid - 1] > nums2[j]) {// i 太大，左移右邊界right = mid - 1;} else {// i 太小，右移左邊界left = mid;}}int i = left;int j = (m + n + 1) / 2 - i;// 處理邊界值：左半部分或右半部分為空的情況double nums1_left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];double nums1_right = (i == m) ? Integer.MAX_VALUE : nums1[i];double nums2_left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];double nums2_right = (j == n) ? Integer.MAX_VALUE : nums2[j];// 計算中位數if ((m + n) % 2 == 1) {return Math.max(nums1_left, nums2_left);} else {return (Math.max(nums1_left, nums2_left) + Math.min(nums1_right, nums2_right)) / 2.0;}}
}

關鍵邏輯解析

1. 數組交換的意義

將較長數組與較短數組交換，確保二分查找在較短數組上進行，減少二分次數（如 m=3, n=5 時，二分范圍是 0~3 而非 0~5）。

2. 分割點的數學意義

j = (m + n + 1) // 2 - i 保證 左半部分總元素數為 (m+n+1)//2：

• 若 m+n 為奇數，左半部分比右半部分多 1 個元素，中位數是左半部分的最大值；
• 若 m+n 為偶數，左半部分與右半部分元素數相等，中位數是兩部分的中間值平均。

3. 邊界值處理

通過 Integer.MIN_VALUE 和 Integer.MAX_VALUE 處理“左半部分為空”或“右半部分為空”的情況，確保比較邏輯的一致性。

4. 二分循環的細節

使用 (left + right + 1) / 2 向上取整，避免 left 和 right 相鄰時的死循環（如 left=1, right=2 時，mid=2 而非 1，確保范圍縮小）。

該方法通過 二分查找分割點 避免了數組的完全合并，將時間復雜度優化到 O(log(min(m,n)))（等價于 O(log(m+n))），是處理“兩個有序數組中位數”問題的經典方案。