背景
输入两个有序数列
a = [a1, a2, ..., an]， 其中a1<a2<....<an
b = [b1, b2, ...bn]， 其中b1<b2<....<bn
寻找a与b合并后数列的中位数
解题思路
（1）计算ab列表合并后中位数的index
>>>if (len(a)+len(b))%2==0:#偶数
... index = [(len(a)+len(b))/2-1, (len(a)+len(b))/2]
...else:#奇数
... index = [(len(a)+len(b))-1]/2
（4）len_a = 11, len_b = 8, index = 9（从0开始），所以是第10个数
| a |
1 |
2 |
|
|
5 |
|
7 |
8 |
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
|
|
3 |
4 |
|
6 |
|
|
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（5）将问题转化为在合并列表中寻找第10小的元素
（6）将10/2 = 5（如果是奇数的话，向下取整），取ab列表中最小的第5位数
| a |
1 |
2 |
|
|
5 |
|
7 |
8 |
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
|
|
3 |
4 |
|
6 |
|
|
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（7）由于8<11所以第10位最小的元素必定不在a列表的前5个元素中，因此将其剔除
| a |
|
|
|
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
3 |
4 |
6 |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（8）由于剔除了5位前10小的数字，因此问题转化为在剩余列表中寻找第5小的元素，5/2=2...1
| a |
|
|
|
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
3 |
4 |
6 |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（9）同理4<12，剔除b列表的前2位
| a |
|
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
6 |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（10）问题转化为在剩余列表中寻找第3小的元素，3/2=1...1
| a |
|
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
6 |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（11）同理6<9，剔除b列表的前1位
| a |
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（12）问题转化为在剩余列表中寻找第2小的元素，2/2=1
| a |
9 |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
|
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（13）同理9<10，剔除a列表的前1位
| a |
|
|
12 |
|
14 |
|
16 |
17 |
18 |
|
| b |
10 |
11 |
|
13 |
|
15 |
|
|
|
19 |
（14）问题转化为在剩余列表中寻找最小的元素，10<12，因此中位数为10
复杂度分析
时间复杂度：O(log(m+n))，其中 m 和 n 分别是数组a和b的长度。初始时有中位数k=(m+n)/2 或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是 O(log(m+n))。
