# -*- coding: utf-8 -*-
"""
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nms1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。
所以只要解决了第k小数的问题，原问题也得以解决
首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。
这两个元素比较共有三种情况：>、<和=。
如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，
所以我们可以将其抛弃。
当A[k/2-1]>B[k/2-1]时存在类似的结论。
当A[k/2-1]=B[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素，我们将其记为m。由于在A和B中分别有k/2-1个元素小于m，
所以m即是第k小的数。(这里可能有人会有疑问，如果k为奇数，则m不是中位数。这里是进行了理想化考虑，在实际代码中略有不同，是先求k/2，然后利用k-k/2获得另一个数。)
"""
def findKth(a,m,b,n,k):
"""
m <= n
:param nums1: 数组A
:param m: 数组A的长度
:param nums2: 数组B
:param n: 数组B的长度
:param k: 第k小的数
:return:
"""
if m > n:
return findKth(b,n,a,m,k)
if (m==0):
return b[k-1]
if (k==1):
return min(a[0],b[0])
# divide k into two parts
pa = min(int(k/2),m) # 相当于 k/2
pb = k-pa
print(pa,pb)
if a[pa-1] < b[pb-1]:
# 把 索引<= pa-1 的去掉之后，索引就从 pa开始了
return findKth(a[pa:],m-pa,b,n,k-pa)
elif a[pa-1] > b[pb-1]:
return findKth(a,m,b[pb:],n-pb,k-pb)
else:
return a[pa-1]
def find_median_sotrted_list(a,m,b,n):
total = m+n
if total&0x1: # k的二进制中最右边的数字
return findKth(a,m,b,n,int(total/2)+1)
else:
return (findKth(a,m,b,n,int(total/2))+findKth(a,m,b,n,int(total/2)+1))/2
a = [1,2,3,4,5]
b = [2,3,4,5,6,7]
print(find_median_sotrted_list(a,len(a),b,len(b)))
参考文献：
https://www.cnblogs.com/bonelee/p/10217507.html