现在的位置: 首页 > 综合 > 正文

快速找到两个有序数组第(m+n)/2个元素

2014年01月07日 ⁄ 综合 ⁄ 共 165字 ⁄ 字号 评论关闭

 题目:

两个数组,分别按从小到大排列
第一个数组,m个元素
第二个数组,n个元素
如何快速找到第(m+n)/2个元素?
能否在O(lg(m+n))的时间复杂度内完成?

 

解题思路:

如果A[m/2] < B[n/2],在A的后半段和B的前半段继续2分查找
如果       >       ,在A的前半段和B的后半段继续2分查找
如果       =,返回

抱歉!评论已关闭.