int partition(int[] a, int lo, int hi, int k) {
        int p = lo + (hi - lo) / 2;
        int storeIndex = lo;
        swap(a, p, hi);
        for (int i = lo; i < hi; i++) {
            if (a[i] < a[hi]) {
                swap(a, i, storeIndex);
                storeIndex++;
            }
        }

        swap(a, storeIndex, hi);
        if (storeIndex == k)
            return a[storeIndex];
        else if (k < storeIndex)
            return partition(a, lo, storeIndex - 1, k);
        else
            return partition(a, storeIndex + 1, hi, k);
    }
This is quick select algorithm and average time complexity is O(N).
We use k as a pivot.
src/problems/medium/KthLargestElementinanArray.java