Order Statistics: Minimum, Maximum, Median and k-th element

In this article, we are going to do some small researches about Order Statistics. Given a unsorted array, we need to find an elements that is k-th when that array is sorted. When k=0, we have the minimum element. If k=array.length-1, we have the maximum. We may also need to find the median of the array.
In part 1, we will examine the case of minimum and maximum with some little interesting problems.
If you think that this is easy for you, you can skip to part 2 where we discuss solving the general problem in linear time.

Part 1: Special Cases
I. Finding Minimum or Maximum
This is pretty easy problem. Below is the code for finding minimum. For finding maximum, it is similar. To solve this problem, we need to use n-1 comparisons where n is the length of the array.

public int findMinimum(int[] a){

    //We assume the array has at least 1 element        
    int min = a[0];
    for(int i=1; i<a.length; i++){
        if(a[i] < min)
            min = a[i];
    }
    return min;
}

II. Finding Minimum and Maximum
There are cases that we need to find both minimum and maximum of an unsorted array. We can easily find them by using the above algorithm. However, it requires 2 * (n-1) comparisons. We can do better in terms of number of comparisons! Pause yourself for a few seconds to think about it.

In order to solve this, we pick 2 elements at a time. We compare the smaller element with the current min, and the bigger element with the current max, and update min and max accordingly. The number of comparisons is around 3/2 * n.

public int[] findMinAndMax(int[] a){
    //we assume that the array has at least 2 elements
    int min = a[0]>a[1]?a[1]:a[0];
    int max = a[0]>a[1]?a[0]:a[1];
    
    int l = a.length % 2 == 0? a.length:a.length-1;
    int smaller, bigger;
    for(int i = 2; i<l;i+= 2){
        if(a[i] > a[i+1]){
            smaller = a[i+1]; bigger = a[i];
        }else{
            smaller = a[i]; bigger = a[i+1];
        }
        if (min > smaller) min = smaller;
        if (max < bigger) max = bigger;
    }
    
    if(a.length % 2 == 1){
        if(a[a.length-1] > max) max = a[a.length-1];
        else if (a[a.length-1] < min) min = a[a.length-1] ;
    }
    int result[] = new int[]{min, max};
    return result;
}

III. Finding the Second Smallest
To find the second smallest we can easily do it with 2 * n comparisons. And again, we can do better with only (roughly) n + lgn comparisons.
We solve this using divide and conquer approach. First, we find the smallest and second smallest of the first half of the array, then find the smallest of second smallest of the second half of the array. Then we can combine the results of the 2 halves. Below is the java code.

public int findSecondSmallest(int[] a){

    //We assume that the array has at least 2 elements
    return findMinAnd2ndSmallest(a, 0, a.length-1)[1];
} 

//find min & second smallest
private int[] findMinAnd2ndSmallest(int[] a, int start, int end){
    if(start == end) return new int[]{a[start], Integer.MAX_VALUE};
    int[] left = findMinAnd2ndSmallest(a, start, (start+end) / 2);
    int[] right = findMinAnd2ndSmallest(a,(start+end) / 2+1, end);
    int smallest = 0, secondSmallest = 0;
    if(left[0] < right[0]) { 
        smallest = left[0]; secondSmallest = right[0];
        if(right[0] > left[1]) secondSmallest = left[1];
    }else {
        smallest = right[0]; secondSmallest = left[0];
        if(left[0] > right[1]) secondSmallest = right[1];
    }
    return new int[]{smallest, secondSmallest};
}

Part 2: General Cases