import java.util.Arrays;
import java.util.Random;

public class CountingSearch {

    public static final Random RAND = new Random();

    public static void main(String[] args) {
        long countLS, countSLS, countBS;
        int[] numbers;
        int target;

        // get started
        printIntroduction();
        numbers = makeIntArray();
        target = getTarget();

        // count ops in linear search
        countLS = linearSearch(numbers, target);

        // sort array for later searches
        Arrays.sort(numbers);

        // count ops in sorted linear search
        countSLS = sortedLinearSearch(numbers, target);

        // count ops in binary search
        countBS = binarySearch(numbers, target);

        // report results
        System.out.println();
        System.out.println("Counting Results:");
        System.out.printf("%25s: %,20d%n", "Linear Search", countLS);
        System.out.printf("%25s: %,20d%n", "Sorted Linear Search", countSLS);
        System.out.printf("%25s: %,20d%n", "Binary Search", countBS);
        System.out.println();
    }

    // print an introduction
    private static void printIntroduction() {
        System.out.println("\n"
                + "Comparing Operation Counts\n"
                + "--------------------------\n\n"
                + "This program compares the number of steps it takes "
                + "to search a large array for a\ntarget number. "
                + "Run it multiple counts to see "
                + "how little the count data varies.");
    }

    // make a large array of large numbers
    private static int[] makeIntArray() {
        int[] result = new int[100000];
        for (int i = 0; i < result.length; ++i) {
            result[i] = getTarget();
        }
        return result;
    }

    // generate a lanrge number randomly
    private static int getTarget() {
        return RAND.nextInt(0, Integer.MAX_VALUE);
    }

    // doa linear search of an unsorted array
    private static int linearSearch(int[] numbers, int target) {
        int count = 0;
        for (int number : numbers) {
            ++count;
            if (number == target) {
                return count;
            }
        }
        return count;
    }

    // search a sorted array for a value, linearly
    private static int sortedLinearSearch(int[] numbers, int target) {
        int count = 0;
        for (int number : numbers) {
            ++count;
            int diff = number - target;
            if (diff == 0) {
                return count;
            } else if (diff > 0) {
                return count;
            }
        }
        return count;
    }

    /// search an array for a value using binary splits
    private static int binarySearch(int[] numbers, int target) {
        int count = 0;
        int low = 0;
        int high = numbers.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            ++count;
            int diff = target - numbers[mid];
            if (diff < 0) {
                // target is smaller
                high = mid;
            } else if (diff > 0) {
                // target is larger
                low = mid + 1;
            } else {
                return count;
            }
        }
        return count;
    }

}