两个等大小有序数组，怎样才能找出他们的中间值？

折半查找，思考一下试试

Minemineㄟ无心 发表于 2014-9-19 10:39
折半查找，思考一下试试

效率太低了。

King_L 发表于 2014-9-19 10:44
效率太低了。

什么叫“等大小有序数组”、“等大小有序数组的中间值”？举个具体例子？

fantacyleo 发表于 2014-9-19 12:17
什么叫“等大小有序数组”、“等大小有序数组的中间值”？举个具体例子？ ...

数组长度相等，而且两个数组都是排好序的。

King_L 发表于 2014-9-19 14:31
数组长度相等，而且两个数组都是排好序的。

那什么叫“他们的中间值”？比如{1,2,3,5} 和{4,6,7,9}，怎么算中间值？

fantacyleo 发表于 2014-9-19 14:35
那什么叫“他们的中间值”？比如{1,2,3,5} 和{4,6,7,9}，怎么算中间值？

你可以想像成是奇数的数组。我描述的就是当时面试官问我的。他就是那么问的。别的什么都没说。所以我也不太清楚。

King_L 发表于 2014-9-19 14:58
你可以想像成是奇数的数组。我描述的就是当时面试官问我的。他就是那么问的。别的什么都没说。所以我也不 ...

。。。。。。你说分奇偶，我似乎有点明白了，实际上是要找两个数组合并后，也就是{1 2 3 4 5 6 7 9}的中位数？

fantacyleo 发表于 2014-9-19 15:01
。。。。。。你说分奇偶，我似乎有点明白了，实际上是要找两个数组合并后，也就是{1 2 3 4 5 6 7 9}的中 ...

大概是的

King_L 发表于 2014-9-20 09:46
大概是的

嗯，这样的话不难。因为两个数组分别有序，那就可以仿照归并排序的合并阶段，将2个有序数组合并为新的有序数组，然后取中间下标的元素即可，时间复杂度是O(n)，n为2个数组的长度。

fantacyleo 发表于 2014-9-20 11:51
嗯，这样的话不难。因为两个数组分别有序，那就可以仿照归并排序的合并阶段，将2个有序数组合并为新的有 ...

如果不合并呢？

King_L 发表于 2014-9-20 15:00
如果不合并呢？

当然没有必要完全合并，因为每个数组长度是ｋ，那么合并到第ｋ个数即可，它就是所求的中间值了