Test287.java

public class Test287 {

  public static int binarysearch(int a[], int k) {
    return binarysearch(a, k, 0, a.length);
  }

  public static int binarysearch(int a[], int k, int lo, int hi) {
    if (lo == hi) return -1;

    int p = (lo + hi) / 2;

    if (k < a[p]) {
      return binarysearch(a, k, lo, p);
    } else if (k > a[p]) {
      return binarysearch(a, k, p + 1, hi);
    }

    return a[p];
  }

  public static int quickselect(int a[], int n) {
    return quickselect(a, n, 0, a.length);
  }

  public static int quickselect(int a[], int n, int lo, int hi) {
    if (lo == hi - 1) return a[lo];

    int p = partition(a, lo, hi);
    int q = p - lo;

    if (n < q) {
      return quickselect(a, n, lo, p);
    } else if (n > q) {
      return quickselect(a, n - q - 1, p + 1, hi);
    }

    return a[p];
  }

  public static int partition(int a[], int lo, int hi) {
    int p = (lo + hi) / 2;
    int pv = a[p];

    swap(a, p, hi - 1);

    int i = lo;
    for (int j = lo; j < hi - 1; j++) {
      if (a[j] < pv) {
        swap(a, i, j);
        i++;
      }
    }

    swap(a, i, hi - 1);
    return i;
  }

  public static void swap(int a[], int i, int j) {
    int d = a[i];
    a[i] = a[j];
    a[j] = d;
  }

  public static void main(String args[]) {
     int a[] = new int[] { 1, 6, 10, 4, 12, 2, 134 };

     for (int i = 0; i < a.length; i++) {
         System.out.println("" + i + "th max = " + quickselect(a, i));
     }
  }
}