MathUtils { public static <T extends Comparable<T>> int randomizedSelect(List<T> a, int lower, int upper, int i) { if (a.isEmpty()) { return -1; } if (lower == upper) { return lower; } int pivot = randomizedPartition(a, lower, upper); int lowerPartitionElementCount = pivot - lower + 1; if (i == lowerPartitionElementCount) { return pivot; } else if (i < lowerPartitionElementCount) { return randomizedSelect(a, lower, pivot - 1, i); } else { return randomizedSelect(a, pivot + 1, upper, i - lowerPartitionElementCount); } } private  MathUtils(); static boolean almostEqual(double a, double b, double delta); static double round(double a, double precision); static double floor(double a, double precision); static double ceil(double a, double precision); static int binarySearch(double[] a, double key); static int binarySearchFloor(double[] a, double key); static int binarySearchCeil(double[] a, double key); static T limit(T value, T min, T max); static double limit(double value, double min, double max); static float limit(float value, float min, float max); static int limit(int value, int min, int max); static int randomizedSelect(List<T> a,
			int lower, int upper, int i); static double magnitude(double base, double n); static double quantile(List<Double> values, double q); static boolean isCalculatable(Number n); static boolean isCalculatable(double n); static double normalizeDegrees(double angle);  }
@Test public void testRandomizedSelect() { List<Double> a = Arrays.asList(13.0, 5.0, 8.0, 3.0, 1.0, 2.0, 1.0); for (int i = 0; i < a.size(); i++) { assertEquals(i, MathUtils.randomizedSelect(a, 0, a.size() - 1, i + 1)); } assertEquals(2, Collections.frequency(a, 1.0)); assertEquals(1, Collections.frequency(a, 2.0)); assertEquals(1, Collections.frequency(a, 3.0)); assertEquals(1, Collections.frequency(a, 5.0)); assertEquals(1, Collections.frequency(a, 8.0)); assertEquals(1, Collections.frequency(a, 13.0)); List<Double> b = Arrays.asList(); assertEquals(-1, MathUtils.randomizedSelect(b, 0, a.size() - 1, 1)); }