4. Median of Two Sorted Arrays

'''
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)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
'''
class Solution(object):
    def findMedianSortedArrays(self, a, b):
    	n = len(a)+len(b)
    	if n&1:
    		return self.kthSmallest(a,b,n//2+1)
    	else:
    		return (self.kthSmallest(a,b,n//2+1) + self.kthSmallest(a,b,n//2))/2.0
    		
    def kthSmallest(self,a,b,k):
    	if len(a)+len(b) < k:
    		return None
    	i=0
    	j=0
    	flag = True
    	while k>0:
    		if i >= len(a):
    			j+=1
    			flag = False
    		elif j >= len(b):
    			i+=1
    			flag = True
    		elif a[i] <= b[j]:
    			i+=1
    			flag = True
    		elif a[i] > b[j]:
    			j+=1
    			flag = False
    		k-=1
    
    	if flag:
    		return a[i-1]
    	else:
    		return b[j-1]