SortedSearch.java
SortedSearch.java — 4.4 KB
Dateiinhalt
import java.util.*; public class SortedSearch { private static abstract class Search { public abstract int search(Integer[] array, Integer elem); } private static class BinarySearch extends Search { @Override public int search(Integer[] array, Integer elem) { // Write your implementation here. } } private static class SparseSearch extends Search { @Override public int search(Integer[] array, Integer elem) { // Write your implementation here. } } // No more tasks below this line. private static class LinearSparseSearch extends Search { @Override public int search(Integer[] array, Integer elem) { if (array == null) { return -1; } for (int i=0; i < array.length; i++) { if (array[i] != null && array[i] == elem) { return i; } } return -1; } } private static final String RESET = "\u001B[0m"; private static final String RED = "\u001B[31m"; private static final String GREEN = "\u001B[32m"; private static void printColor(String msg, String color) { System.out.println(color + msg + RESET); } private static boolean runTest(Integer[] array, Search algo) { System.out.println("Testing array: " + Arrays.toString(array)); HashSet<Integer> inArray = new HashSet<Integer>(); // Test elements in array for (Integer elem : array) { if (elem == null) continue; int result = algo.search(array, elem); if (result < 0 || result >= array.length) { printColor("Element " + elem + " not found.", RED); return false; } inArray.add(elem); } for (Integer elem = -150; elem <= 150; ++elem) { if (inArray.contains(elem)) continue; int result = algo.search(array, elem); if (result != -1) { printColor("Element " + elem + " not in array: expected -1, got " + result, RED); return false; } } printColor("Pass", GREEN); return true; } private static Integer[] getCopy(Integer[] array) { Integer[] copy = new Integer[array.length]; System.arraycopy(array, 0, copy, 0, copy.length); return copy; } public static void main(String[] args) { Random rnd = new Random(42); Search binSearch = new BinarySearch(); int binSearchTests = 0, binSearchTestsPassed = 0; for (int size = 1; size <= 20; ++size) { for (int test = 0; test < 5; ++test) { Integer[] array = new Integer[size]; for (int i = 0; i < size; ++i) array[i] = rnd.nextInt(201) - 100; Arrays.sort(array); ++binSearchTests; if (runTest(array, binSearch)) ++binSearchTestsPassed; } } Search sparseSearch = new SparseSearch(); int sparseSearchTests = 0, sparseSearchTestsPassed = 0; double[] nullProb = {0, 0.25, 0.5, 0.75, 1}; for (int size = 1; size <= 20; ++size) { for (int test = 0; test < 5; ++test) { Integer[] array = new Integer[size]; for (int i = 0; i < size; ++i) array[i] = rnd.nextInt(201) - 100; Arrays.sort(array); for (double prob : nullProb) { Integer[] copy = getCopy(array); // Generate nulls for (int i = 0; i < size; ++i) if (rnd.nextDouble() < prob) copy[i] = null; ++sparseSearchTests; if (runTest(copy, sparseSearch)) ++sparseSearchTestsPassed; } } } printColor("Binary search: " + binSearchTestsPassed + "/" + binSearchTests + " tests passed", binSearchTestsPassed == binSearchTests ? GREEN : RED); printColor("Sparse search: " + sparseSearchTestsPassed + "/" + sparseSearchTests + " tests passed", sparseSearchTestsPassed == sparseSearchTests ? GREEN : RED); } }