c++ - 高效的中值计算

Question

我有一个长度为 n 的数组 A。假设 B 是一个包含 A 的第 k 个元素的数组(我们永远不想单独存储 - 这只是为了帮助解释)。我想找到 B 的中位数，我想将 A 的那个元素移动到A中第(n/2)层的位置。

我怎样才能有效地做到这一点？我正在考虑尝试对 std::nth_element 进行一次调用，将指针传递给 A。但是，我需要此指针递增 A 的 k 个元素。我该怎么做？本质上:

A2 = (kFloat *)A;
std::nth_element(A2, A2 + (n/k)/2, A2 + (n/k));
swap(A[ ((n/k)/2)*k ], A[n/2]); // This might be redundant

其中 kFloat 是一个结构，其作用类似于 float ，但当您增加指针时，它会在内存中移动 k*sizeof(float)。

注意:我不需要真正的中位数(当 n 为偶数时中间两个的平均值)。

编辑:另一种表达我想要的方式(不编译，因为 k 不是常量):

std::nth_element((float[k] * )A, ((float[k] * ) A)[(n / k) / 2], ((float[k] * ) A)[n / k]);

编辑 2: 我正在更改 algorithm.cc，所以我不想引入对像 Boost 这样的库的依赖。我只想使用核心 C++11 功能 + std。

Answer 1

我已经在自定义迭代器上实现了一次二分搜索 - 你可以在 https://gist.github.com/IvanVergiliev/6048716 查看它.它针对的是一个特定的问题，但总体思路是相同的:在您的序列上编写一个迭代器类并实现所需的运算符(++、--、+=)以一次移动 k 个位置。