# Median Of Two Sorted Arrays
###### tags `leetcode`
To reach O(N) or O(logN), a prune and search methodolegy is required. For each iteration, we must discard at least 1/4 or 1/2 dataset. The simplest algorithm is Binary Search

## Median-of-two-sorted-arrays/solution/
https://leetcode.com/problems/median-of-two-sorted-arrays/solution/

Why ```i + j = (m − i) + (n − j) + 1```
Because partition is one more than the length of m+n

Magic hidden is: we put the median for odd elements in the left part.

I think the most difficult part is the odd/even cases, I want to give some complementary explanation:
Note the presumption in the OP:
1.1 If m + n is even, then split the elements evenly into the left and right part, so i + j = m + n - i - j. (Clearly the 1st middle number is in the left part and the 2nd middle number is in the right part), thus we have i = (m + n)/2 - j (1)
1.2 If m + n is odd, then put the median in the left part, so the number of elements in the left part is one more than that of elements in the right part. That's where + 1 comes in the formula: i + j = m + n - i - j + 1. Thus we have j = (m + n + 1)/2 - i(2)

Then!!! (1) can be merged to (2)! Let's list (1) and (2) together:

(1) j = (m + n)/2 - i, if m + n is even
(2) j = (m + n + 1)/2 - i, if m + n is odd
Notice that if a number num is even, then num/2 = (num + 1)/2, for example 4/2 = (4 + 1)/2 = 2. So (m + n)/2 is equal to (m + n + 1)/2 in (1). Thus we can merge them to (2). That's the reason why we use j = (m + n + 1)/2 - i through our code.

In Python3, integer division should use // instead /

I've tried to stduy the article, but hindered too long, now I decide learn from code and try to abstract the solving methology.

## The Solving Approach
* Since the requirement of O(logN), we can't sort, we must do prune and search!
* Since the array have SORTED, we could apply binary search!
* Therefore, we need figure out how to narrow down the search range.
* Since we have two array, we will have two pointer, and we should find the constrants between two pointer, because when doing binary search, we will change the range of one pointer, and adjust another
* ```j = (m + n + 1) / 2 - i```, 0 <= i <= m, n must grater and equal than m, or j will be negative.

    Ensure
    * len(left_part)=len(right_part)
    * max(left_part)≤min(right_part)


## The Time Consumption
This a hard level problem, it takes me two days.
When read article, don't jump anything.


## The Solution

class Solution:
def findMedianSortedArrays(self, A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError

imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect, consider corner case

if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])

if (m + n) % 2 == 1:
return max_of_left

if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])

return (max_of_left + min_of_right) / 2.0