findPercent.cpp

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

int partition(vector<int>& vec, int left, int right) {
    int pivot = vec[left];
    int l = left + 1;
    int r = right;
    while (l<=r) {
        if (vec[l] > pivot && vec[r] < pivot) {
            std::swap(vec[l], vec[r]);
            l++;
            r--;
        }
        if (vec[l] <= pivot) {
            l++;
        }
        if (vec[r] >= pivot) {
            r--;
        }
    }
    std::swap(vec[r], vec[left]);
    cout <<vec[r] <<endl;
    return r;
}

int findK(vector<int>& vec, int k) {
    int left = 0;
    int right = vec.size()-1;
    int kth;

    while(left <= right) {
        int idx = partition(vec, left, right);
        if (idx == k) {
            kth = idx;
            break;
        }
        if (idx > k) {
            right = idx - 1;
        }
        if (idx < k) {
            left = idx + 1;
        }
    }

    return vec[kth];
}

int findPercent(vector<int> vec, double percent) {
    if (percent <0 || percent >1.0) {
        throw range_error("Invalid percent");
    }
    if (vec.size() == 0) {
        throw length_error("Invalid vector length");
    }
    int n = vec.size();
    int k = (int) (n*percent);
    if (k==n) k=k-1; 
    vector<int> vcopy(vec.begin(), vec.end());

    return findK(vcopy, k);
}


int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(4);
    v.push_back(2);
    v.push_back(5);
    try {
        cout << findPercent(v, 0.5)<<endl;
    }
    catch (exception & e) {
        cerr << e.what() <<endl;
    }
    return 0;
}