题目描述

给出两个有序数组，用o(log(mn ) ) )的时间复杂度求中值的方法

例如，1，4 [ 2，3 ]-2.5

1，6，5-2

如果没有

思路分析

小时复杂度的要求，根据合并排序的想法，可以用o(mn )的时间复杂度来求解；

大致的逻辑如下。

两个指针分别指向两个数组的开头，每次移动更小的元素，直到它们移动到中间位置。只要注意边界的处理和奇偶校验要素的处理即可；

但是，这一时间的复杂性不满足主题描述的要求；

这个问题的前提是有序的数组，因为涉及到搜索元素，所以容易涉及到二分搜索算法

将两个排列分别设为a和b，将要素的个数分别设为m和n；从a的中间要素开始处理，判断这个中间要素在b中的位置，时间复杂度log(n )；

如果找到该位置小于中央值的位置，则取a中位于中间位置和结束位置中间的要素进行判断；

如果是大于中央值的位置，则取a中的开始位置和中间位置的中间要素进行判断；

如果正好是中间值的位置，可以直接处理；

这样的时间复杂度为o(log(mn ) )

元素不在a中时，更换a、b，重复即可；

的总时间复杂度为2*o(log ) mn )，按时间复杂度计算，为o ) log ) mn ) )

因为代码量很大，所以关注源代码并回复“第一周的算法”即可