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);
    }
}