# Median of two Sorted Arrays

**Hard** There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

## Thoughts

先把找中点generalize成找第k个元素。findKth使用了二分的思想，只是和传统二分模板不同，我们用递归做。

## Code

```
class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        if ((A.length + B.length) % 2 == 0) {
            return (findKth(A, 0, B, 0, (A.length + B.length) / 2) + findKth(A,
                    0, B, 0, (A.length + B.length) / 2 + 1)) / 2.0;
        } else {
            return findKth(A, 0, B, 0, (A.length + B.length) / 2 + 1);
        }
    }

    // 从 以A_start和B_start为开始的两个数组所合并的数组中寻找第k大的数
    public int findKth(int[] A, int A_start, int[] B, int B_start, int k) {
        // base-cases
        if (A_start == A.length) {
            return B[B_start + k - 1];
        } else if (B_start == B.length) {
            return A[A_start + k - 1];
        }

        // 相当于A_start + B_start 代表的长度始终比k大1
        // 当k == 1时, 代表仅剩一个元素待取, 从剩下的两个选项中小的优先级高
        if (k == 1) {
            return Math.min(A[A_start], B[B_start]);
        }

        // induction cases
        int A_key = A_start + k / 2 - 1 < A.length ? A[A_start + k / 2 - 1]
                : Integer.MAX_VALUE; // 引入MAX相当于说A已满, 退出竞争
        int B_key = B_start + k / 2 - 1 < B.length ? B[B_start + k / 2 - 1]
                : Integer.MAX_VALUE;
        if (A_key < B_key) {
            return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
        } else {
            return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
        }
    }

}
```

## Analysis

二分法，时间复杂度为O(lg(m+n))


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/median_of_two_sorted_arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.