Intro to Programming - Assignment 8.1 - Question for Dr. Frewen

SearchAlgs.java

// Written by Christopher Turner.

import java.util.*;
public class SearchAlgs {
    public static int getMin(int[] a) { //Finds the minimum value in an array of integers
        int min = 0; //Initializes to 0
        for (int i : a) { //For every item in the array...
            if (i < min) { //If the minimum variable is greater than the current element
                min = i; //Set the minimum variable equal to the current element
            }
        }
        return min; //Return the minimum value
    }

    public static int getMax(int[] a) { //Finds the maximum value in an array of integers
        int max = 0; //Initializes to 0
        for (int i : a) { //For every item in the array...
            if (i > max) { //If the maximum variable is less than the current element
                max = i; //Set the maximum variable equal to the current element
            }
        }
        return max; //Return the maximum value
    }

    public static int[] linearFindValue(int[] a, int desired) {  //Input an integer array and a desired value, output an integer array
        ArrayList<Integer> indices = new ArrayList<Integer>(); //Declare and initialize an arraylist to store indices
        int i = 0; //Create variable to keep track of current index
        for (int n : a) { //For every element 'n' in the array...
            if (n == desired) { //If 'n' is the desired value...
                indices.add(i); //Add the current value of 'i' to the arraylist
            }
            i++; //Increment 'i'
        }
        if (indices.size() == 0) { //If the desired value is not found in the given array...
            if (desired < getMin(a) || desired > getMax(a)) { //And if the desired value is outside of the range of the array...
                indices.add(-2); //Return an index of -2, as per in-class instructions
            }
            else {
                indices.add(-1); //Otherwise return a value of -1, as per convention
            }
        }
        //Converting the arraylist of indices back to an integer array:
        int[] finalIndices = new int[indices.size()]; //Create an array of the proper size
        int z = 0; //Placeholder variable
        for (int n : indices) {
            finalIndices[z] = n;
            z++;
        }
        return finalIndices; //Return array of indices of the desired value from the originally-provided array
    }

    public static int binaryFindValue(int[] a, int desired) { //Input an integer array and a desired value, output an integer
        int lowerBound = 0; //Establish a lower and upper bound of indices to look at from 0
        int upperBound = a.length - 1; //...to the length minus 1.
        int currentIndex = (upperBound + lowerBound) / 2; //Create a variable to store the index currently being checked
        while (lowerBound <= upperBound) { //While the desired value has not yet been found...
            if (a[currentIndex] == desired) { //If the current element of the array is the desired value...
                break;
            }
            if (a[currentIndex] > desired) { //If the current element of the array is greater than the desired value...
                upperBound = currentIndex + 1; //Center focus on the value halfway between index 0 and index currentIndex
            }
            if (a[currentIndex] < desired) { //If the current element of the array is less than the desired value...
                lowerBound = currentIndex - 1; //Center focus on the value halfway between index currentIndex and index a.length - 1
            }
            currentIndex = (upperBound + lowerBound) / 2;
        }
        return currentIndex; //Return the index of the desired value from the originally-provided array
    }

    public static void main(String[] args) {
        int[] array1 = new int[1000]; //Create an integer array of 1,000 elements
        for (int i = 0; i < array1.length; i++) { //For an integer 'i' from 0 to 1,000...
            array1[i] = i; //Set index 'i' of array equal to 'i'
        }
        int[] array2 = new int[10000]; //Create an integer array of 10,000 elements
        for (int i = 0; i < array2.length; i++) { //For an integer 'i' from 0 to 10,000...
            array2[i] = i; //Set index 'i' of array equal to 'i'
        }
        int[] array3 = new int[1000]; //Create an integer array of 1,000 elements
        for (int i = 0; i < array3.length; i++) { //For an integer 'i' from 0 to 1,000...
            array3[i] = (int) (Math.random() * array3.length); //Set index 'i' of array equal to a random integer between 0 and 1,000
        }
        long linearStartTime1 = System.nanoTime();
        linearFindValue(array1,(int) Math.random() * 1000);
        long linearEndTime1 = System.nanoTime();
        long linearDurationTime1 = (linearEndTime1 - linearStartTime1);
        System.out.println("Linear, sorted, 1000 element: " + linearDurationTime1);

        long linearStartTime2 = System.nanoTime();
        linearFindValue(array2,(int) Math.random() * 10000);
        long linearEndTime2 = System.nanoTime();
        long linearDurationTime2 = (linearEndTime2 - linearStartTime2);
        System.out.println("Linear, sorted, 10000 element: " + linearDurationTime2);

        long linearStartTime3 = System.nanoTime();
        linearFindValue(array3,array3[(int) Math.random() * 1000]);
        long linearEndTime3 = System.nanoTime();
        long linearDurationTime3 = (linearEndTime3 - linearStartTime3);
        System.out.println("Linear, unsorted, 1000 element: " + linearDurationTime3);

        long binaryStartTime1 = System.nanoTime();
        binaryFindValue(array1,(int) (Math.random() * 1000));
        long binaryEndTime1 = System.nanoTime();
        long binaryDurationTime1 = (binaryEndTime1 - binaryStartTime1);
        System.out.println("Binary, sorted, 1000 element: " + binaryDurationTime1);

        long binaryStartTime2 = System.nanoTime();
        binaryFindValue(array2,(int) (Math.random() * 10000));
        long binaryEndTime2 = System.nanoTime();
        long binaryDurationTime2 = (binaryEndTime2 - binaryStartTime2);
        System.out.println("Binary, sorted, 10000 element: " + binaryDurationTime2);

        long binaryStartTime3 = System.nanoTime();
        //binaryFindValue(array3,array3[(int) (Math.random() * 1000)]);
        long binaryEndTime3 = System.nanoTime();
        long binaryDurationTime3 = (binaryEndTime3 - binaryStartTime3);
        System.out.println("Binary, unsorted, 1000 element: " + binaryDurationTime3);

        long javaStartTime1 = System.nanoTime();
        Arrays.binarySearch(array1,(int) Math.random() * 1000);
        long javaEndTime1 = System.nanoTime();
        long javaDurationTime1 = (javaEndTime1 - javaStartTime1);
        System.out.println("Java, sorted, 1000 element: " + javaDurationTime1);

        long javaStartTime2 = System.nanoTime();
        Arrays.binarySearch(array2,(int) Math.random() * 10000);
        long javaEndTime2 = System.nanoTime();
        long javaDurationTime2 = (javaEndTime2 - javaStartTime2);
        System.out.println("Java, sorted, 10000 element: " + javaDurationTime2);

        long javaStartTime3 = System.nanoTime();
        Arrays.binarySearch(array3,array3[(int) Math.random() * 1000]);
        long javaEndTime3 = System.nanoTime();
        long javaDurationTime3 = (javaEndTime3 - javaStartTime3);
        System.out.println("Java, unsorted, 1000 element: " + javaDurationTime3);
    }
}