Question

Make a package a5. To this package, add SearchTest.java (Links to an external site.) with starter code for the assignment. You will want to carefully read the comments in this file to see where you need to add code.

Search Experiment

In this assignment you will measure the relative performance of binary search and sequential search on different length arrays. The basic idea is to make an array of random values, sort them, and then compare the performance of binary search and sequential search by searching for different key values.

There are many ways to compare performance. For example, the amount of time spent getting an answer is one way. However, even this simple measure has complications. For example, if part of the experiment is run while playing a game on the same computer, this can distort results. Another issue is that code can run so fast on a computer that it is difficult to capture meaningful timings.

Instead, you will use a simple measure - the number of times a the search loop iterates while searching for the key. This is related to the execution time.

Example binary search and sequential search are implemented in the starter code file. Your job is to copy and modify those so they do not return an index value, but instead the number of times the search loop iterates.

Then, write code in the specified methods to use an array of test data, pick a random key, and search for that key. Since the randomness makes it possible for a particular search to find the key the first time it looks, the experiment code repeats the process of picking a random key and counting the search steps for a number of times. Finally, the results are averaged and returned to main, where the results are summarized. In main, add a loop to report results for different length arrays.

For example, a (very small) test array might look like

[1, 2, 4, 4, 5]

If the number of tests to be run is 3, you would run binary search on that array for three randomly chosen keys, like 1, 4, and 5. Then you would run sequential search for the same array for three randomly chosen keys, like 2, 1, 5. If the number of tests to be run is large enough, the specific keys are not likely to change the results.

You will count up the iterations for each key, add them up, and divide by the number of tests to get an average.

Then, repeat the process for a different-sized array.

You will have to generate random numbers for this. There is an example in the code, and you also made random numbers in Lab 4. Please refer to those instructions or resources from the Internet to remind yourself how that works.

Decide what different sizes of arrays will provide insight into the relative performance of the search techniques. In addition, the bigger the repetitions value, the more accurate the average will be - something like a 100 repetitions is probably fine for this experiment. Record the average for each method in a table with the type of search, the size of the array, and average search count.

Write up a short document in a word processing system (Google docs, MS Word, laTEX) showing the table and a graph where the x axis is the length of the array and the y axis is the average iterations for that size array. Then discuss why you chose the array sizes you tested and what trends you see in the experimental data. A paragraph is likely a reasonable length for discussion. Add your name, assignment, and class to the document. Create a pdf (usually a "Save as" or "Print to" pdf is a mechanism to do that) called SearchReport.pdf.

You do not need to write tests for this assignment. However, you should be carefully checking your code using prints or informal tests that you will remove before submitting. You should interpret the table and graph to see if they make sense given what you know of the behavior of these search approaches.

CODE:

package a5;

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

/**
 * This class compares the number of operations needed to search using
 * sequential search and binary search.
 * 
 * 
 *
 */
public class SearchTest {

        /**
         * The main method controls the rest of the program. It determines the size of
         * the array to be tested, the number of tests to be done per array, and then
         * runs the tests and outputs some results.
         * 
         * Change this to loop over a range of array sizes such that the results provide
         * insight into the behavior of binary search vs. sequential search.
         * 
         * @param args
         */
        public static void main(String[] args) {

                // MODIFY: Make a loop here to test different array sizes. Running
                // the program should report on average search costs for several sizes.
                int testArraySize = 1_000;
                int numberofTestsPerArray = 100;
                int[] testArray = randomSortedFill(testArraySize);
                double sequentialResults = testNRepetitionsSequential(testArray, numberofTestsPerArray);
                double binaryResults = testNRepetitionsBinary(testArray, numberofTestsPerArray);
                System.out.println("For an array of size " + testArraySize + " the average search costs are:");
                System.out.println("     binaryAvg    : " + binaryResults + " iterations");
                System.out.println("     sequentialAvg: " + sequentialResults + " iterations");
        }

        /**
         * The method tests how many search loop iterations, on average, are needed to
         * search a given int array for different key values using sequential search.
         * The array has values ranging from 0 to length of the array - 1.
         * 
         * Pick a random key in that same range of values. Search for this key in the
         * array and measure the number of search loop iterations by using the
         * methods that need to be implemented below.
         * 
         * Repeat this search on the same array but a new key for numberOfTests times.
         * 
         * Calculate the average tests using the total number of search iterations and the
         * number of tests.
         * 
         * @param randomSortedNumbers: an array of ints filled with random sorted
         *                             values.
         * @param numberOfTests:       the number of times to repeat the tests. Must be
         *                             greater than 0.
         * @return the average iterations used to search the array.
         * 
         */
        public static double testNRepetitionsSequential(int[] randomSortedNumbers, int numberOfTests) {
                return 0.0; // change this code to return the average iterations
        }

        /**
         * The method tests how many search loop iterations, on average, are needed to
         * search a given int array for different key values using binary search.
         * The array has values ranging from 0 to length of the array - 1.
         * 
         * Pick a random key in that same range of values. Search for this key in the
         * array and measure the number of search loop iterations by using the
         * methods that need to be implemented below.
         * 
         * Repeat this search on the same array but a new key for numberOfTests times.
         * 
         * Calculate the average tests using the total number of search iterations and the
         * number of tests.
         * 
         * @param randomSortedNumbers: an array of ints filled with random sorted
         *                             values.
         * @param numberOfTests:       the number of times to repeat the tests. Must be
         *                             greater than 0.
         * @return the average iterations used to search the array.
         * 
         */
        public static double testNRepetitionsBinary(int[] randomSortedNumbers, int numberOfTests) {
                return 0.0; // change this code to return the average iterations
        }

        /**
         * Given a length, make an int array of that length and fill the array with
         * random values from 0 to length-1 (inclusive) int values. Use the Random class
         * to generate these values. The array can have duplicate values, this is not a
         * shuffle of all values from 0 to length-1, but instead length values picked
         * randomly from 0 to length-1.
         * 
         * The values are then sorted in ascending order.
         * 
         * This method has been implemented for you. You do not need to change the
         * documentation for this method.
         * 
         * @param length: the length of an array to be filled with random values.
         * @return the array of sorted random values.
         */
        public static int[] randomSortedFill(int length) {
                Random generator = new Random();
                int[] randomArray = new int[length];
                for (int index = 0; index < randomArray.length; index++) {
                        randomArray[index] = generator.nextInt(length);
                }
                Arrays.sort(randomArray);

                return randomArray;
        }

        /**
         * Search values for the key using binary search. Assumes values is sorted in
         * ascending order. This code is provided as a reminder of how binary search
         * works. You do not need to run it or modify it.
         * 
         * @param values a sorted array of values
         * @param key    the value being searched for
         * @return the index where key is found, or -1 otherwise.
         */
        public static int binarySearchForKey(int[] values, int key) {
                int lo = 0;
                int hi = values.length - 1;
                while (lo <= hi) {
                        int mid = lo + (hi - lo) / 2;
                        if (values[mid] == key)
                                return mid;
                        else if (values[mid] < key)
                                lo = mid + 1;
                        else // if (vals[mid] > key) is the only case left, so we don't need to check it.
                                hi = mid - 1;
                }
                return -1;
        }

        /**
         * Search values for the key using binary search. Assumes values is sorted in
         * ascending order. Count the number of times the search loop repeats.
         * 
         * @param values a sorted array of values
         * @param key    the value being searched for
         * @return the number of search loop iterations.
         */
        public static int binarySearchForKeyWithCount(int[] values, int key) {
                return 0; // change this code
        }

        /**
         * Search values for the key using sequential search. This code is provided as
         * a reminder of how sequential search works. You do not need to run it or
         * modify it.
         * 
         * @param values a sorted array of values
         * @param key    the value being searched for
         * @return the index where key is found, or -1 otherwise.
         */
        public static int sequentialSearchForKey(int[] values, int key) {
                for (int index = 0; index < values.length; index++) {
                        if (key == values[index])
                                return index;
                }
                return -1;
        }

        /**
         * Search values for the key using sequential search. Assumes values is sorted in
         * ascending order. Count the number of times the search loop repeats.
         * 
         * @param values a sorted array of values
         * @param key    the value being searched for
         * @return the number of search loop iterations.
         */

        public static int sequentialSearchForKeyWithCount(int[] values, int key) {
                return 0; // change this code
        }

}

Answer 1

package a5;

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

/**
* This class compares the number of operations needed to search using
* sequential search and binary search.
*
*
*
*/

public class SearchTest {

   /**
* The main method controls the rest of the program. It determines the size of
* the array to be tested, the number of tests to be done per array, and then
* runs the tests and outputs some results.
*
* Change this to loop over a range of array sizes such that the results provide
* insight into the behavior of binary search vs. sequential search.
*
* @param args
*/
public static void main(String[] args) {
  
   // set start array size to 1000
   int testArraySize = 1000;
int numberofTestsPerArray = 100; // number of times tests is done on the array size
  
// loop from 1,000 to 10,000
   while(testArraySize <= 10000)
   {
       // create a random sorted array
       int[] testArray = randomSortedFill(testArraySize);
  
       // get the average iterations for sequential search
   double sequentialResults = testNRepetitionsSequential(testArray, numberofTestsPerArray);
   // get the average iterations for binary search
   double binaryResults = testNRepetitionsBinary(testArray, numberofTestsPerArray);
   System.out.println("For an array of size " + testArraySize + " the average search costs are:");
   System.out.println(" binaryAvg : " + binaryResults + " iterations");
   System.out.println(" sequentialAvg: " + sequentialResults + " iterations");
  
   testArraySize += 1000; // increment array size by 1000
   }
}
  
/**
* The method tests how many search loop iterations, on average, are needed to
* search a given int array for different key values using sequential search.
* The array has values ranging from 0 to length of the array - 1.
*
* Pick a random key in that same range of values. Search for this key in the
* array and measure the number of search loop iterations by using the
* methods that need to be implemented below.
*
* Repeat this search on the same array but a new key for numberOfTests times.
*
* Calculate the average tests using the total number of search iterations and the
* number of tests.
*
* @param randomSortedNumbers: an array of ints filled with random sorted
* values.
* @param numberOfTests: the number of times to repeat the tests. Must be
* greater than 0.
* @return the average iterations used to search the array.
*
*/
public static double testNRepetitionsSequential(int[] randomSortedNumbers, int numberOfTests) {
int totalIterations = 0;
int searchIndex;
Random ran = new Random();
   // loop numberOfTests times
for(int i=0;i<numberOfTests;i++)
   {
       searchIndex = ran.nextInt(randomSortedNumbers.length); // randomly generate an index between [0, array length -1]
       // add the iterations required to search to totalIterations
       totalIterations += sequentialSearchForKeyWithCount(randomSortedNumbers, randomSortedNumbers[searchIndex]);
   }
  
// calculate and return the average iterations
   if(numberOfTests > 0)
       return ((double)totalIterations)/numberOfTests;
   return 0.0;
}

  
/**
* The method tests how many search loop iterations, on average, are needed to
* search a given int array for different key values using binary search.
* The array has values ranging from 0 to length of the array - 1.
*
* Pick a random key in that same range of values. Search for this key in the
* array and measure the number of search loop iterations by using the
* methods that need to be implemented below.
*
* Repeat this search on the same array but a new key for numberOfTests times.
*
* Calculate the average tests using the total number of search iterations and the
* number of tests.
*
* @param randomSortedNumbers: an array of ints filled with random sorted
* values.
* @param numberOfTests: the number of times to repeat the tests. Must be
* greater than 0.
* @return the average iterations used to search the array.
*
*/
public static double testNRepetitionsBinary(int[] randomSortedNumbers, int numberOfTests) {
  
   int totalIterations = 0;
int searchIndex;
Random ran = new Random();
   // loop numberOfTests times
for(int i=0;i<numberOfTests;i++)
   {
       searchIndex = ran.nextInt(randomSortedNumbers.length); // randomly generate an index between [0, array length -1]
       // add the iterations required to search to totalIterations
       totalIterations += binarySearchForKeyWithCount(randomSortedNumbers, randomSortedNumbers[searchIndex]);
   }
  
// calculate and return average iterations
   if(numberOfTests > 0)
       return ((double)totalIterations)/numberOfTests;
   return 0.0;
}
  
/**
* Given a length, make an int array of that length and fill the array with
* random values from 0 to length-1 (inclusive) int values. Use the Random class
* to generate these values. The array can have duplicate values, this is not a
* shuffle of all values from 0 to length-1, but instead length values picked
* randomly from 0 to length-1.
*
* The values are then sorted in ascending order.
*
* This method has been implemented for you. You do not need to change the
* documentation for this method.
*
* @param length: the length of an array to be filled with random values.
* @return the array of sorted random values.
*/
public static int[] randomSortedFill(int length) {
Random generator = new Random();
int[] randomArray = new int[length];
for (int index = 0; index < randomArray.length; index++) {
randomArray[index] = generator.nextInt(length);
}
Arrays.sort(randomArray);

return randomArray;
}
  
/**
* Search values for the key using binary search. Assumes values is sorted in
* ascending order. This code is provided as a reminder of how binary search
* works. You do not need to run it or modify it.
*
* @param values a sorted array of values
* @param key the value being searched for
* @return the index where key is found, or -1 otherwise.
*/
public static int binarySearchForKey(int[] values, int key) {
int lo = 0;
int hi = values.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (values[mid] == key)
return mid;
else if (values[mid] < key)
lo = mid + 1;
else // if (vals[mid] > key) is the only case left, so we don't need to check it.
hi = mid - 1;
}
return -1;
}

  
/**
* Search values for the key using binary search. Assumes values is sorted in
* ascending order. Count the number of times the search loop repeats.
*
* @param values a sorted array of values
* @param key the value being searched for
* @return the number of search loop iterations.
*/
public static int binarySearchForKeyWithCount(int[] values, int key) {
int low = 0, high = values.length-1, mid;
int iterations = 0; // initialize iterations to 0
// loop that continues until it is a valid range
while(low <= high)
{
   iterations++; // increment number of iterations
   mid = (low+high)/2; // get the mid index
   if(values[mid] == key) // check value at mid = key, exit the loop
       break;
   else if(values[mid] < key) // value at mid < key, then key must be present in right subarray
       low = mid + 1;
   else                       // value at mid > key, then key must be present in left subarray
       high = mid - 1;
}
  
return iterations;
}

/**
* Search values for the key using sequential search. This code is provided as
* a reminder of how sequential search works. You do not need to run it or
* modify it.
*
* @param values a sorted array of values
* @param key the value being searched for
* @return the index where key is found, or -1 otherwise.
*/
public static int sequentialSearchForKey(int[] values, int key) {
for (int index = 0; index < values.length; index++) {
if (key == values[index])
return index;
}
return -1;
}
  
/**
* Search values for the key using sequential search. Assumes values is sorted in
* ascending order. Count the number of times the search loop repeats.
*
* @param values a sorted array of values
* @param key the value being searched for
* @return the number of search loop iterations.
*/

public static int sequentialSearchForKeyWithCount(int[] values, int key) {
  
   // loop over the array
   for(int i=0;i<values.length;i++)
   {
       if(values[i] == key) // ith value = key, return (i+1) as number of iterations required
           return (i+1);
   }
  
   return values.length; // key not found, return the length of array
}

}

// end of program

Output: