-------------------------------------------------------------------------------------------

// File: Lab4Driver.java // Author: Geoffrey Tien/ Rita Ester // Date: 2017-01-24 // Description: Driver file for CSCI 225 Lab 4 (running time)

import java.util.Random;

public class Lab4Driver { private static Random r = new Random(System.nanoTime()); public static void main(String[] args) { long startTime, stopTime; double usedTime_ms; boolean arrayIsOrdered = false; // change this as part of your experiments int arraySize = 100000; // change this as part of your experiments int maxNumber = 150000; // change this as part of your experiments int target = (int) (r.nextDouble() * maxNumber); int targetIndex = -1; int[] array1 = createIntArray(arrayIsOrdered, arraySize, maxNumber); startTime = System.nanoTime(); targetIndex = linearSearch(array1, target); stopTime = System.nanoTime(); usedTime_ms = (stopTime-startTime); System.out.print("Statistics: LINEAR SEARCH "); if (targetIndex == -1) System.out.print("(failed): "); else System.out.print("(success): "); System.out.println(usedTime_ms/1000 + " microseconds"); if (arrayIsOrdered) { startTime = System.nanoTime(); targetIndex = binarySearch(array1, target); stopTime = System.nanoTime(); usedTime_ms = (stopTime-startTime); System.out.print("Statistics: BINARY SEARCH "); if (targetIndex == -1) System.out.print("(failed): "); else System.out.print("(success): "); System.out.println(usedTime_ms/1000 + " microseconds"); } } // creates, populates, and returns an array of random (positive) integers up to the specified maximum value // PARAMS: arrayIsOrdered - whether the should be arrayIsOrdered or random // numElements - the number of elements in the // maxValue - the upper limit of elements public static int[] createIntArray(boolean arrayIsOrdered, int numElements, int maxValue) { int[] array = new int[numElements]; int number; for (int i = 0; i

while (low

if (target == array[mid]) return mid; else if (target > array[mid]) low = mid + 1; else //target 0; i--) { int temp = array[0]; array[0] = array[i]; array[i] = temp; n = n-1; swapDown(array, n, 0); } } // Puts unordered array into heap structure public static void heapify(int[] array) { for (int i = array.length/2; i >= 0; i--) swapDown(array, array.length-1, i); } // Restores heap property downwards public static void swapDown(int[] array, int num, int i) { int left = 2*i; int right = 2*i + 1; int largest; if (left array[i]) largest = left; else largest = i; if (right array[largest]) largest = right; if (largest != i) { int temp = array[i]; array[i] = array[largest]; array[largest] = temp; swapDown(array, num, largest); } } }

CSCI 225 Lab exercise 4 Measuring running time In this lab you will be timing how long it takes for two search algorithms to complete. Download the Lab4Driver.java file from C4; add it to a new Java project, then extend and run it. This file generates a random integer array, sorts it, and then performs linear search and binary search for a target item. Description of parameters in Lab4Driver.java arrayIsOrdered (boolean) - whether the array will be sorted or not before running the search. If the array is unordered, only linear search will be performed. If the array is ordered, both linear search and binary search will be performed. arraySize (int) - the number of elements in the array maxNumber (int) - determines the largest integer that can be generated. A large value for maxNumber with a relatively small arraySsize will reduce the probability of generating duplicate values, and a smaller probability of success for finding the random search key. A small value for maxNumber increases the chance of duplicate values and search success. Experiment with different combinations of arraySize and maxNumber, and see how the running time is affected. Try increasing by factors of 2, 5, 10, etc Average search times Modify the main method to perform 500 searches (not just one). To compare Linear and Binary Search, use the same rray Record the running times for successful (target element found) and for unsuccessful searches (target element not found) separately, and calculate the average times for successful and unsuccessful searches Record your results in the table below, adding your own choices for arraySize and maxNumber: Running time, (microseconds) arraySize: 100,000arraySize: maxNumber: arraySize maxNumber: maxNumber: 150,000