寻找两个正序数组的中位数

2020-07-29 15:47:34 +08:00
 linxiaoziruo

二分法的解法的关键步骤是 "上下数组分别取第 numm=k//2 个数，进行对比，若 nums1[numm] <= nums2[numm]，则说明 nums1 的前面这 numm 个数肯定小于目标数"。

为什么 "说明 nums1 的前面这 numm 个数肯定小于目标数"? 一直想不明白。

1501 次点击
所在节点    Java
3 条回复
HeiWuBai
2020-07-29 16:18:21 +08:00
二分查找是基于数组排列好的 好像
lidlesseye11
2020-07-29 19:58:31 +08:00
它们既小于自己的后半截，也小于另一个的后半截，所以肯定小于中位数
（边界条件先不讨论。。
linxiaoziruo
2020-07-30 07:49:04 +08:00
@lidlesseye11 妙啊

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/694061

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX