public int median(int[] nums) {
        // write your code here
        // int n = nums.length;
        int n = nums.length;
        int k = n / 2;
        if (n % 2 == 0)
            k = n / 2 - 1;
        int begin = 0, end = n - 1;
        // boolean k1 = false, k2 = false;
        while (true) {
            int position = helper(nums, begin, end);
            if (position == k) {
                break;
            } else if (position < k) {
                begin = position + 1;
            } else {
                end = position - 1;
            }
        }
        return nums[k];
    }