# 4. Median of Two Sorted Arrays

## Tóm tắt đề
Cho 2 dãy $A, B$ với độ dài $m, n$ đã được sắp xếp. Tính trung vị của dãy sắp xếp gộp bởi 2 dãy này.

## Yêu cầu
Thuật toán phải có độ phức tạp là $\mathcal{O}(\log (m + n))$.

## Lời giải

Không mất tính tổng quát, giả sử $m \le n$.

Có nhiều cách giải, chúng ta sẽ đi từ cách hiển nhiên nhất đến cách nhanh nhất.

### $\mathcal{O}((m + n) \log (m + n))$

Gộp 2 dãy lại, sort rồi in ra trung vị.

### $\mathcal{O}(m + n)$

Đặt $k = \lceil{\frac{m + n}{2}} \rceil$. Ta cần tìm nhanh $k$ phần tử nhỏ nhất trong 2 dãy này.

1 nhận xét hiển nhiên: vì 2 dãy đã được sắp xếp, nên $k$ phần tử nhỏ nhất này được tạo bởi $i$ phần tử đầu tiên của $A$ và $k - i$ phần tử đầu tiên của $B$.

Ta sẽ lấy $i$ phần tử đầu tiên của $A$, và $k - i$ phần tử đầu tiên của $B$, rồi kiểm tra xem đó có đúng là $k$ phần tử nhỏ nhất của mảng ban đầu hay không. Tức là phần tử lớn nhất trong $k$ phần tử được chọn phải $\ge$ phần tử nhỏ nhất trong $m + n - k$ phần tử còn lại. Hay chúng ta có thể viết: $\max(A_i, B_{k - i}) \le \min(A_{i + 1}, B_{k - i + 1})$.


Nếu $(m + n)$ chẵn, thì đáp án là trung bình cộng của $\max(A_i, B_{k - i})$ và $\min(A_{i + 1}, B_{k - i + 1})$.

Nếu lẻ, thì đáp án chính là $\max(A_i, B_{k - i})$.

Như vậy chúng ta đã có thuật toán $\mathcal{O}(m + n)$.

### $\mathcal{O(\log (m + n))}$

Để đạt được độ phức tạp này, chúng ta cần tận dụng triệt để điều kiện cả 2 dãy đã được sắp xếp, $A_i \le A_{i + 1}$ và $B_i \le B_{i + 1} \ \forall i$.

Thế nên, nếu cách chia ở $i$ không thoả mãn, tức là $\max(A_i, B_{k - i}) > \min(A_{i + 1}, B_{k - i + 1})$, thì chỉ có 2 khả năng xảy ra:

1. Nếu $A_i > B_{k - i + 1}$, thì $k$ phần tử nhỏ nhất không chứa $A_i$ trở về sau, hay nói cách khác, phải giảm $i$ xuống.
2. Nếu $B_{k - i} > A_{i + 1}$, thì $k$ phần tử nhỏ nhất không chứa $B_{k - i}$ trở về sau, hay nói cách khác chúng ta phải tăng $i$ lên.

Bởi 2 dấu hiệu này mà chúng ta có thể tìm nhanh được vị trí $i$ bằng chặt nhị phân. Do đó độ phức tạp cuối cùng là $\mathcal{O}(\log(m + n))$.

### Lời giải
https://leetcode.com/problems/median-of-two-sorted-arrays/submissions/