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

Question

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

// 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 < numElements; i++)
{
// generate a number
number = (int)(r.nextDouble()*maxValue);
array[i] = number;
}

if (arrayIsOrdered)
{
System.out.println("Sorting... ");
heapSort(array);
}
return array;
}
  
// Iterative linear search through an
public static int linearSearch(int[] array, int target)
{
for (int i = 0; i < array.length; i++)
{
if (array[i] == target)
return i;
}
return -1;
}

// Iterative binary search through an
public static int binarySearch(int array[], int target)
{
int low = 0;
int high = array.length - 1;
int mid = 0;

while (low <= high)
{
mid = (low + high) / 2;

if (target == array[mid])
return mid;
else if (target > array[mid])
low = mid + 1;
else //target < array[mid]
high = mid - 1;
}
return -1; //target not found
}
  
// HeapSort and supporting methods
public static void heapSort(int[] array)
{
heapify(array);
int n = array.length-1;
for (int i = n; i > 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 <= num && array[left] > array[i])
largest = left;
else
largest = i;
if (right <= num && array[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

Explanation / Answer

Running Time,(microseconds)

arraySize: 1000,000

maxNumber: 150,000

arraySize: 100

maxNumber: 150,0

arraySize: 1000

maxNumber: 150

Linear Search (unordered, success)

Statistics: LINEAR SEARCH (success): 4.277 microseconds

Statistics: LINEAR SEARCH (success): 5.131 microseconds

Statistics: LINEAR SEARCH (success): 4.277 microseconds

Linear Search (unordered, failure)

Statistics: LINEAR SEARCH (failed): 1868.423 microseconds

Statistics: LINEAR SEARCH (failed): 3.849 microseconds

Statistics: LINEAR SEARCH (failed): 24.376 microseconds

Linear Search (ordered, success)

Statistics: LINEAR SEARCH (success): 5.132 microseconds

Statistics: LINEAR SEARCH (success): 3.849 microseconds

Statistics: LINEAR SEARCH (success): 7.27 microseconds

Linear Search (ordered, failure)

Statistics: LINEAR SEARCH (failed): 2074.98 microseconds

Statistics: LINEAR SEARCH (failed): 3.849 microseconds

Statistics: LINEAR SEARCH (failed): 25.231 microseconds

Binary Search (ordered, success)

Statistics: BINARY SEARCH (success): 8.981 microseconds

Statistics: BINARY SEARCH (success): 4.277 microseconds

Statistics: BINARY SEARCH (success): 4.704 microseconds

Binary Search (ordered, failure)

Statistics: BINARY SEARCH (failed): 3.422 microseconds

Statistics: BINARY SEARCH (failed): 1.711 microseconds

Statistics: BINARY SEARCH (failed): 1.71 microseconds

Running Time,(microseconds)

arraySize: 1000,000

maxNumber: 150,000

arraySize: 100

maxNumber: 150,0

arraySize: 1000

maxNumber: 150

Linear Search (unordered, success)

Statistics: LINEAR SEARCH (success): 4.277 microseconds

Statistics: LINEAR SEARCH (success): 5.131 microseconds

Statistics: LINEAR SEARCH (success): 4.277 microseconds

Linear Search (unordered, failure)

Statistics: LINEAR SEARCH (failed): 1868.423 microseconds

Statistics: LINEAR SEARCH (failed): 3.849 microseconds

Statistics: LINEAR SEARCH (failed): 24.376 microseconds

Linear Search (ordered, success)

Statistics: LINEAR SEARCH (success): 5.132 microseconds

Statistics: LINEAR SEARCH (success): 3.849 microseconds

Statistics: LINEAR SEARCH (success): 7.27 microseconds

Linear Search (ordered, failure)

Statistics: LINEAR SEARCH (failed): 2074.98 microseconds

Statistics: LINEAR SEARCH (failed): 3.849 microseconds

Statistics: LINEAR SEARCH (failed): 25.231 microseconds

Binary Search (ordered, success)

Statistics: BINARY SEARCH (success): 8.981 microseconds

Statistics: BINARY SEARCH (success): 4.277 microseconds

Statistics: BINARY SEARCH (success): 4.704 microseconds

Binary Search (ordered, failure)

Statistics: BINARY SEARCH (failed): 3.422 microseconds

Statistics: BINARY SEARCH (failed): 1.711 microseconds

Statistics: BINARY SEARCH (failed): 1.71 microseconds

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.