• T(n) = T(n/2) + n, O(n)

import java.util.*;
import javafx.util.*;

public class N
{
	public static int nth(int [] array, int p, int r, int i)
	{
		if(p == r)
			return array[p];
		int q = randomPartition(array, p, r);
		int k = q-p+1;
		if(i==k)
			return array[q];
		else if(i < k)
			return nth(array, p, q-1, i);
		else
			return nth(array, p+1, r, i-k);
	}

	public static int randomPartition(int [] array, int p, int r)
	{
		Random ran = new Random();
		int i = ran.nextInt(r-p+1);
		i = p+i;

		int temp = array[r];
		array[r] = array[i];
		array[i] = temp;

		return partition(array, p, r);
	}

	public static int partition(int [] array, int p, int r)
	{
		int pivot = array[r];
		int i = p-1;
		for(int j = p; j < r; j++)
		{
			if(array[j] < pivot)
			{
				i++;
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[i+1];
		array[i+1] = array[r];
		array[r] = temp;

		return i+1;
	}

	public static int [] getArray(int n)
	{
		int [] array = new int[n];
		Random r = new Random();

		for(int i = 0; i < n; i++)
			array[i] = r.nextInt(100);

		return array;
	}

	public static void display(int [] array)
	{
		for(int e : array)
			System.out.printf("%5d", e);
		System.out.println();
	}

	public static void main(String args[])
	{
		int [] array = getArray(100);

		display(array);

		System.out.println("2nd: "+nth(array, 0, array.length-1, 1));
	}
}
			

• CLRS Chapter 9