代码之家 › 专栏 › 技术社区 › James

阻塞问题的一种算法设计[C++代码]

median-of-medians logarithm binary-search recursion algorithm

1

James · 技术社区 · 8 年前

A[1..N] 和 B[1..N] 中提供了升序

Q: 设计 一 O(log N)-time 中值的 N可能不是2的幂 .

为了让事情变得简单,我们可以假设 O(1) 返回的算法 m

2^m < N <  2^m+1

我的问题:

1 回复 | 直到 8 年前

1

4

Tim Biegeleisen 8 年前

你可以在 O(logN) 时间使用二进制搜索方式。考虑以下两个阵列:

1 1 2 2 3
1 2 3 4 5

现在,组合中值为:

1 1 1 2 2 2 3 3 4 5 => 2

让我们看看如何找到它。首先猜测中值是每个阵列的中心:

1 1 2 2 3 => 2
1 2 3 4 5 => 3

大于2或 更大的 之间 2和第二个数组中的所有内容 更大的 大于3。这不会影响中间带的位置,因为我们正在丢弃上的元素数 二者都

2 2 3 => 2
1 2 3 => 2

该算法的性能与二进制搜索一样好,即 O(logN) .

推荐文章

Serge Rogatch · 在AVX2中高效实现log2(_uuM256d)

8 年前

James · 阻塞问题的一种算法设计[C++代码]

8 年前

qwark · C++中非常快速的近似对数(自然对数)函数?

8 年前

jorgen · 与Alglib一样,使用Eigen快速获取行列式的对数

9 年前

user2946696 · 没有java.lang.Math的二进制对数?

11 年前

R_User · 如何将线性回归绘制为双对数R图?

11 年前