Median of Two Sorted Arrays: binary search trên partition, không phải trên giá trị

Constraint của bài là O(log(m+n)). Một dòng đó loại bỏ gần như mọi approach bạn nghĩ đến đầu tiên — sort, scan, merge — và chỉ thẳng vào binary search. Nhưng binary search trên cái gì? Không có giá trị nào để tìm ở đây; bạn muốn median, là một vị trí, không phải một target. Insight mà bài toán đang test là bạn có thể binary search trên một partition point thay vì một giá trị. Tất cả những gì còn lại đều rút ra từ đó.

Đề bài

Cho hai mảng đã sắp xếp nums1 và nums2 có kích thước lần lượt là m và n, trả về median của tất cả phần tử gộp lại trong thời gian O(log(m+n)). Full statement: LeetCode 4.

Ràng buộc:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6

Constraints thực sự ép buộc điều gì

m và n mỗi mảng tối đa 1000, và m + n >= 1. Cả hai mảng đã được sắp xếp. Giá trị nằm trong [-10^6, 10^6].

Constraint đã sắp xếp là thứ đang làm phần lớn công việc. Mảng đã sắp xếp có nghĩa là bạn có thể binary search — không chỉ trên giá trị, mà trên vị trí. Nếu bạn chọn một điểm cắt trong nums1, điểm cắt tương ứng trong nums2 được xác định luôn: cộng lại hai nửa trái phải chứa đúng (m+n)/2 phần tử (hoặc (m+n+1)/2 nếu bạn xử lý tổng lẻ). Vậy bạn chỉ tìm kiếm trên một chiều dù có hai mảng. Điều đó thu hẹp search space từ m * n xuống còn O(min(m, n)).

Giới hạn giá trị [-10^6, 10^6] có một hệ quả thực tế: bạn cần sentinel infinity tại các biên mảng. Khi partition đặt cut ở đầu hoặc cuối mảng, không có left maximum hay right minimum thực sự — bạn cần +inf và -inf làm placeholder. Python và C# xử lý điều này gọn gàng.

Approach 1: Merge rồi tìm median

Cách đọc thẳng của bài toán — merge cả hai mảng đã sắp xếp, rồi chọn phần tử giữa — là O(m+n) time và O(m+n) space. Không đáp ứng yêu cầu bài toán, nhưng là baseline đúng và đáng implement trước để đảm bảo bạn hiểu phép tính median trước khi thêm độ phức tạp của binary search vào.

Merge dùng two-pointer sweep giống merge sort:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        merged = []
        i, j = 0, 0
 
        while i < len(nums1) and j < len(nums2):
            if nums1[i] <= nums2[j]:
                merged.append(nums1[i])
                i += 1
            else:
                merged.append(nums2[j])
                j += 1
 
        while i < len(nums1):
            merged.append(nums1[i])
            i += 1
 
        while j < len(nums2):
            merged.append(nums2[j])
            j += 1
 
        n = len(merged)
        if n % 2 == 1:
            return float(merged[n // 2])
        else:
            return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        var merged = new List<int>();
        int i = 0, j = 0;
 
        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] <= nums2[j]) merged.Add(nums1[i++]);
            else merged.Add(nums2[j++]);
        }
 
        while (i < nums1.Length) merged.Add(nums1[i++]);
        while (j < nums2.Length) merged.Add(nums2[j++]);
 
        int n = merged.Count;
        if (n % 2 == 1) return (double)merged[n / 2];
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    }
}

Phần odd/even split ở bước cuối là chi tiết hay gây lỗi: với tổng lẻ, median là phần tử duy nhất ở giữa tại index n // 2; với tổng chẵn, là trung bình của hai index n // 2 - 1 và n // 2. Sai ở đây và mọi output sẽ lệch nửa bước.

Time: O(m + n). Bạn chạm mỗi phần tử một lần trong merge. Space: O(m + n). List merged chứa tất cả phần tử.

Approach này không thỏa constraint thời gian của bài toán. Nhưng đây là bước đầu đúng — xác nhận logic median trên các ví dụ trước khi chuyển sang binary search.

Approach 2: Binary search trên partition point

Đây là ý tưởng cốt lõi. Bạn muốn tách tổng m + n phần tử thành nửa trái và nửa phải sao cho mọi phần tử ở nửa trái nhỏ hơn hoặc bằng mọi phần tử ở nửa phải. Khi tồn tại split đó, median được xác định: max(left) với tổng lẻ, (max(left) + min(right)) / 2 với tổng chẵn.

Bạn không cần thử tất cả vị trí để tìm split. Vì cả hai mảng đã sắp xếp, nếu bạn lấy cut1 phần tử từ bên trái nums1 và cut2 phần tử từ bên trái nums2 (với cut1 + cut2 == half), thứ duy nhất cần kiểm tra là liệu các phần tử biên có bị chéo nhau không:

• nums1[cut1 - 1] <= nums2[cut2] (left max của nums1 không vượt right min của nums2)
• nums2[cut2 - 1] <= nums1[cut1] (left max của nums2 không vượt right min của nums1)

Nếu cả hai điều kiện đúng, bạn có partition đúng. Nếu điều kiện đầu sai, cut1 quá lớn — trượt trái. Nếu điều kiện hai sai, cut1 quá nhỏ — trượt phải. Đó chính là vòng lặp binary search.

Luôn binary search trên mảng ngắn hơn. Điều đó cho O(log(min(m,n))) iterations, và đảm bảo cut tương ứng trên mảng dài hơn luôn trong bounds.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        # Luôn binary search trên mảng ngắn hơn
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
 
        m, n = len(nums1), len(nums2)
        total = m + n
        half = total // 2  # kích thước mục tiêu của nửa trái
 
        left, right = 0, m
 
        while left <= right:
            cut1 = (left + right) // 2
            cut2 = half - cut1
 
            # Sentinel boundary xử lý partition rỗng gọn gàng
            maxLeft1  = float('-inf') if cut1 == 0 else nums1[cut1 - 1]
            minRight1 = float('inf')  if cut1 == m else nums1[cut1]
            maxLeft2  = float('-inf') if cut2 == 0 else nums2[cut2 - 1]
            minRight2 = float('inf')  if cut2 == n else nums2[cut2]
 
            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
                # Tìm được partition đúng
                if total % 2 == 1:
                    return float(min(minRight1, minRight2))
                else:
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
            elif maxLeft1 > minRight2:
                right = cut1 - 1   # cut1 quá lớn, trượt trái
            else:
                left = cut1 + 1    # cut1 quá nhỏ, trượt phải
 
        return 0.0  # không bao giờ đến đây với input hợp lệ

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // Luôn binary search trên mảng ngắn hơn
        if (nums1.Length > nums2.Length) {
            int[] tmp = nums1; nums1 = nums2; nums2 = tmp;
        }
 
        int m = nums1.Length, n = nums2.Length;
        int total = m + n;
        int half = total / 2;
 
        int left = 0, right = m;
 
        while (left <= right) {
            int cut1 = (left + right) / 2;
            int cut2 = half - cut1;
 
            int maxLeft1  = cut1 == 0 ? int.MinValue : nums1[cut1 - 1];
            int minRight1 = cut1 == m ? int.MaxValue : nums1[cut1];
            int maxLeft2  = cut2 == 0 ? int.MinValue : nums2[cut2 - 1];
            int minRight2 = cut2 == n ? int.MaxValue : nums2[cut2];
 
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if (total % 2 == 1)
                    return Math.Min(minRight1, minRight2);
                return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
            }
            else if (maxLeft1 > minRight2)
                right = cut1 - 1;
            else
                left = cut1 + 1;
        }
 
        return 0.0;
    }
}

Phiên bản C# dùng int.MinValue và int.MaxValue làm sentinel thay vì float infinity. Logic so sánh vẫn đúng, nhưng lưu ý: nếu total % 2 == 0 và maxLeft1 = int.MaxValue, phép tính trung bình sẽ overflow. Trên thực tế search kết thúc trước khi đạt trường hợp đó — nhưng nếu bạn muốn chắc chắn, dùng long cho phép tính trung bình hoặc dùng cách tiếp cận float như Python.

Time: O(log(min(m,n))). Mỗi iteration halves search range trên mảng ngắn hơn. Space: O(1). Không có mảng phụ; chỉ vài biến integer.

Trace partition: Example 1, nums1 = [1,3], nums2 = [2]

Total = 3 (lẻ), half = 1. Binary search trên nums1 (length 2).

Partition sau vị trí 1 trong nums1 cho left = [1] từ nums1, left = [] từ nums2. Nửa phải là [3] và [2]. max(1, -inf) = 1, min(3, 2) = 2. Vì total lẻ, return min(minRight1, minRight2) = 2. Đúng.

Trace partition: Example 2, nums1 = [1,2], nums2 = [3,4]

Total = 4 (chẵn), half = 2. Binary search trên nums1 (cả hai cùng length 2, không quan trọng cái nào).

Hai iterations. Cut đầu tiên (cut1=1) đặt [1] từ nums1 và [3] từ nums2 vào bên trái — nhưng maxLeft2 = 3 > minRight1 = 2, nghĩa là phía trái nums2 có phần tử quá lớn. Trượt cut1 sang phải. Cut thứ hai (cut1=2, cut2=0) lấy toàn bộ nums1 vào bên trái và không gì từ nums2 vào bên trái. Lúc này maxLeft1 = 2, minRight2 = 3. Tất cả điều kiện thỏa mãn, median là (2 + 3) / 2 = 2.5.

Các edge case thực sự quan trọng

Một mảng rỗng (nums1 = [], nums2 = [5]): Sau swap, nums1 vẫn là [] với m = 0. Vòng binary search chạy một lần với cut1 = 0, cut2 = half. Sentinel cut1 == 0 kích hoạt, maxLeft1 = -inf. Điều kiện partition đúng ngay. Median được tính từ nums2 một mình. Đúng.

Tất cả phần tử mảng này nhỏ hơn mảng kia (nums1 = [1,2], nums2 = [3,4]): Binary search hội tụ về cut1 = 2, cut2 = 0 — partition "lấy hết nums1, không lấy gì từ nums2". Example 2 ở trên trace chính xác trường hợp này.

Duplicate elements xuyên mảng (nums1 = [1,1], nums2 = [1,1]): Điều kiện partition dùng <=, không phải <. Duplicate tại biên là ổn — maxLeft1 <= minRight2 đúng khi chúng bằng nhau. Median tính ra đúng là 1.0.

Mảng đơn phần tử (nums1 = [1], nums2 = [2]): Total là 2 (chẵn). Iteration đầu: cut1 = 0, cut2 = 1. maxLeft2 = 2 > minRight1 = 1 — trượt phải. cut1 = 1, cut2 = 0: maxLeft1 = 1, minRight2 = 2. Thỏa mãn. Median là (1 + 2) / 2 = 1.5.

Total lẻ vs chẵn: Khi total % 2 == 1, median là phần tử giữa duy nhất — min(minRight1, minRight2). Khi chẵn, là trung bình của largest-left và smallest-right. Sai công thức này là bug phổ biến nhất khi adapt code từ trường hợp chỉ có lẻ hoặc chỉ có chẵn.

Bảng so sánh

Merge approach không chỉ chậm hơn — nó cấp phát một mảng lớn bằng union cả hai input. Với m + n = 2000 thì ổn. Nhưng nếu bạn hình dung scale lên streaming data hay mảng rất lớn, việc cấp phát đó là vấn đề thực sự. Phiên bản binary search dùng một số biến cố định bất kể kích thước input.

Pattern mà bài này dạy

Đây là ví dụ rõ ràng nhất trong series binary-search về nghĩa "binary search trên answer space" là gì như một kỹ thuật. Giá trị bạn tìm không nằm trong mảng — đó là partition point. Bạn định nghĩa một invariant (partition hợp lệ khi hai điều kiện cross-boundary đúng), bạn có một adjustment rule đơn điệu (trượt cut1 trái khi maxLeft1 quá lớn, trượt phải nếu ngược lại), và binary search hội tụ.

Cấu trúc tương tự xuất hiện trong nhiều bài trông không giống bài search lúc đầu: "tìm capacity nhỏ nhất để ship tất cả gói trong D ngày," "tìm divisor nhỏ nhất để tổng không vượt threshold," "tìm phần tử nhỏ thứ k trong sorted matrix." Tất cả đều rút về: định nghĩa valid là gì, binary search cho ranh giới, trích xuất đáp án.

Tôi sẽ ship phiên bản binary search. Merge là stepping stone hữu ích để verify logic median, nhưng khi đã đúng, không có lý do để giữ lại. Binary search là O(1) space và constraint nói O(log(m+n)) — đó là điều bài toán được thiết kế để thưởng.

Vị trí trong series binary-search

Đây là bài khó nhất trong series cho đến nay. Các bài trước — classic binary search, search in rotated sorted array, find minimum in rotated array, search a 2D matrix — đều tìm kiếm một giá trị tại một vị trí. Bài này tìm kiếm một vị trí thỏa mãn một điều kiện về giá trị. Sự đảo ngược đó là bước nhảy khái niệm.

Find K-th Smallest Element in Two Sorted Arrays (generalization của bài này): median chỉ là phần tử thứ k = (m+n)/2. Binary search tổng quát hóa trực tiếp cho bất kỳ k nào, không chỉ phần tử giữa.

Kth Smallest Element in a Sorted Matrix (LeetCode 378): binary search trên value space, dùng hàm đếm để kiểm tra có bao nhiêu phần tử <= mid. Axis tìm kiếm khác, cấu trúc giống nhau.

Find K-th Smallest Pair Distance (LeetCode 719): binary search trên distance, đếm các cặp có distance <= mid. Cùng template "binary search trên answer, dùng feasibility check."

Find Median from Data Stream (LeetCode 295): nếu phần tử đến một lúc một cái thay vì trong hai mảng tĩnh, bạn cần hai heap — max-heap cho nửa trái và min-heap cho nửa phải. Invariant giống nhau (left max <= right min), nhưng data structure khác vì bạn không thể random-access một stream.