@Test public void findMedian() { List<Integer> input = Arrays.asList(3,2,4,5,1,6); Assert.assertEquals(3, QuickSelect.findMedian(input).intValue()); for (int i = 0; i < 10; i++) { int N = (i+1) * 100; input = Shuffler.getRandomList(N, -N / 2, N / 2); List<Integer> expect = new ArrayList<>(input); Collections.sort(expect); Assert.assertEquals(expect.get((N - 1) / 2), QuickSelect.findMedian(input)); } }
public static <E> E findMedian(List<E> input, Comparator<E> comparator) { int k = (input.size() - 1) / 2; return quickSelect(input, k, 0, input.size() - 1, comparator); }
QuickSelect { public static <E> E findMedian(List<E> input, Comparator<E> comparator) { int k = (input.size() - 1) / 2; return quickSelect(input, k, 0, input.size() - 1, comparator); } }
QuickSelect { public static <E> E findMedian(List<E> input, Comparator<E> comparator) { int k = (input.size() - 1) / 2; return quickSelect(input, k, 0, input.size() - 1, comparator); }  }
QuickSelect { public static <E> E findMedian(List<E> input, Comparator<E> comparator) { int k = (input.size() - 1) / 2; return quickSelect(input, k, 0, input.size() - 1, comparator); }  static E findMedian(List<E> input, Comparator<E> comparator); static E findMedian(List<E> input); static E findKth(List<E> input, int k); }
QuickSelect { public static <E> E findMedian(List<E> input, Comparator<E> comparator) { int k = (input.size() - 1) / 2; return quickSelect(input, k, 0, input.size() - 1, comparator); }  static E findMedian(List<E> input, Comparator<E> comparator); static E findMedian(List<E> input); static E findKth(List<E> input, int k);  }