---
tags: LeetCode,Top 100 Liked Questions
---
# 4. Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
## 題目敘述
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
## Example
Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

## 解題想法
此題的難處於其time complexity is O(log (m+n))(不能sort再取Median)
且是兩個已排序的array
1.binary search

(1)令array長度為m,n
Median可分成m+n為偶數或奇數討論
偶數的Median位置->int((m+n+1)/2) int(m+n+2)/2)
奇數的位置->(m+n+1)/2
由此可得到Median位置->int((m+n+1)/2) int((m+n+2)/2)(奇數的會是同一個)

(2)求兩個array中的第k位置
兩個array使用兩個變數i,j記錄起始位置

a.若i>m or j>n 即k不再前/後array->在另一array找

b.若k=1 -> k為i,j中較小值

c.若不為以上情況 則比較兩個array中的Median

將較小array的起始位置往前k/2位置,並將k也減少k/2(binary seach的精神)
(因array的Median較小->其array的前k/2個數都較小可以跳過)
若array沒有k/2個->不能跳過(不能比較)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(),n=nums2.size();
        return (find_kthnum(nums1,0,nums2,0,(m+n+1)/2)+find_kthnum(nums1,0,nums2,0,(m+n+2)/2))/2.0;
    }
    int find_kthnum(vector<int>& nums1,int i,vector<int>& nums2,int j,int k){
        if(i>=nums1.size()){ //a.i>m k不再前array
            return nums2[j+k-1];
        }
        if(j>=nums2.size()){ //a.j>n k不再後array
            return nums1[i+k-1];
        }
        if(k==1){
            return min(nums1[i],nums2[j]); //b.若k=1 -> k為i,j中較小值
        }
        
        int mid1=0,mid2=0;
        if((i+k/2-1)>=nums1.size()){
            mid1=INT_MAX; //array沒有k/2個 不能跳過
        }
        else{
            mid1=nums1[i+k/2-1];
        }
        if((j+k/2-1)>=nums2.size()){
            mid2=INT_MAX; //array沒有k/2個 不能跳過
        }
        else{
            mid2=nums2[j+k/2-1];
        }
        
        if(mid1<mid2){  //較小array的起始位置往前k/2位置,並將k也減少k/2
            return find_kthnum(nums1,i+k/2,nums2,j,k-k/2);
        }
        else{
            return find_kthnum(nums1,i,nums2,j+k/2,k-k/2);
        }
    }
};