c++ - 从C++中的整数集合确定第三个四分位数？

我正在阅读Accelerated C++。目前，我处于第3章的结尾，这是我要尝试的练习:

“编写程序以计算和打印一组整数的四分位数。”

我找到了第一和第二个四分位数，但是我不知道如何找到第三个四分位数。这是我的代码:

 #include <algorithm>
 #include <iostream>
 #include <vector>
 using namespace std;

 int main(){
    cout<<"Enter numbers:";
    int x;
    vector<int>integers;
    while(cin>>x)
        integers.push_back(x);

    typedef vector<int>::size_type vec_sz;
    vec_sz size = integers.size();
    sort(integers.begin(), integers.end());
    vec_sz mid = size/2;
    vec_sz q1 = mid/2;
    double median;
    median = size % 2 == 0 ? ((double)integers[mid] + (double)integers[mid-1]) / 2
: integers[mid];
    double quartOne = ((double)integers[q1] + (double)integers[q1-1])/2;
    cout<<"The First Quartile is: "<<quartOne<<endl;
    cout<<"The Second Quartile is: "<<median<<endl;
    return 0;
}

最佳答案

一种方法是对集合进行排序，然后采用3个划分项:

vector<int> v = ...;
sort(v.begin(), v.end());
int q12 = v[v.size()*1/4];
int q23 = v[v.size()*2/4];
int q34 = v[v.size()*3/4];

数据项的数量为O(nlogn)。

另一种方法是分别对三个分区的数据执行二进制搜索。例如，提出一个初始q12，通过传递数据来检查它是否正确，如果不正确，则将其向上或向下调整一半，然后重复。对q23和q34同样进行。

从技术上讲，这是O(n)，因为32位int具有固定范围，并且可以在最多32个遍中进行二进制搜索。