Formatted question description: https://leetcode.ca/all/4.html

# 4. Median of Two Sorted Arrays

Hard

## Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = 

The median is 2.0


Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


## Solution

Use the idea of binary search. First of all, if nums1.length > nums2.length, then swap the two arrays nums1 and nums2.

Next, search in the shorter array nums1 to make the algorithm more efficient. Initially let low be 0 and high be nums1.length. Each time set index1 = (high - low) / 2 + low, and let index2 = (nums1.length + nums2.length + 1) / 2 - index1. If nums1[index1] < nums2[index2 - 1], then set low = index1 + 1. If nums1[index1 - 1] > nums2[index2], then set high = index1 - 1. Otherwise, if the sum of the two arrays’ lengths is odd, then the median is either nums1[index1 - 1] or nums2[index2 - 1]. If the sum of the two arrays’ lengths is even, then the other element that determines the median is either nums1[index1] or nums[index2]. Calculate the median accordingly.

Why is it ““target/2”” ??? For example, [1,3,5,…,99], [2,4,6,…,100] two cases

1. A total of 100 numbers, then the 50th in all sorts. The average number from the two arrays is 25 numbers each
2. If it is not average, then [1,2,3,…,50], [51,52,…,100] are all taken from the first array, that is, the first 25 must be From the first array

case m is much longer than n midIndex/2 to check private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {

### Pitfalls

1. The k in dfs is the number of several, not the index. But start/end is index
2. leftMedian and rightMedian are also numbers, not index int leftMedian = (m + n + 1) / 2; int rightMedian = (m + n + 2) / 2;
3. dfs termination condition k==1 if (k == 1) { return Math.min(nums1[start1], nums2[start2]); }

solution-2: The optimal solution O(log min(m,n)), a short array of binary search

Java