/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// Find k largest element (k = n/2)

void PrintVector(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        std::cout << nums[i] << " ";
    }
    std::cout << std::endl;
}

int MedianUtil(vector<int>& nums, int left, int right, int k) {

    if (k > 0 && k <= (right - left + 1)) {

        int pivot = nums[right];
        int j = left - 1;
        for (int i = left; i <= right - 1; ++i) {
            if (nums[i] <= pivot) {
                ++j;
                swap(nums[i], nums[j]);
            }
        }
        ++j;
        swap(nums[j], nums[right]);

        if (j - left == k - 1)
            return nums[j];
        if (j - left > k - 1)
            return MedianUtil(nums, left, j - 1, k);

        return MedianUtil(nums, j + 1, right, k - j + left - 1);
    }

    return numeric_limits<int>::min();
}

int Median(vector<int>& nums) {

    return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);

}

int main()
{
    vector<int> nums{0,2,3,1,6,4};
    // 1 1 2 2 3 6
    PrintVector(nums);

    std::cout << Median(nums) << std::endl;

    return 0;
}