Comparative Analysis of Linear and Binary Search Algorithms

Comparative Analysis of Linear and Binary Search Algorithms

In chapter #14 we discussed the linear and binary search algorithms. We showed that linear
search has a worst-case time complexity of O(n). We also showed that the binary search
algorithm has a worst-case time complexity of O(log n). While linear search does not require
the data to be sorted, binary search only works if the data is sorted.
Comparing these algorithms is somewhat unfair since most of the work required to perform
binary search is spent in sorting the data. There are occasions when linear search outperforms
binary search when the search key is at the head of the sorted data. In today’s laboratory
session, you will do an empirical comparative analysis of the performance of these algorithms
using runtime as a metric.
The StopWatch Class
Use this class (see Big Java 8/e, pp. 633-634) to measure run times. This class is included
in the starter code archive file for lab # 8 and available for download on Moodle. Note that the
start method, starts the clock if it is not already running and the stop method stops the clock
and updates the elapsed time. The getElapsedTime returns the total time in milliseconds the
clock has been running since the last time the reset method was called. The reset method sets
the elapsed time to 0.
The ArrayUtil Class
This class is also included in the starter code archive available for download on Moodle. The
original is from Big Java 8/e, pp. 630-631. I made some modifications to the randomIntArray
method so that it returns Integer[] rather than int[]. In lab # 7, you were asked to implement the
following methods:
1. public static Integer[] descIntArray(int length): returns an array of integers in descending
order - (length − 1),(length − 2), · · · , 1, 0.
2. public static Integer[] ascIntArray(int length): returns an array of integers in ascending
order - 0, 1, · · · ,(length − 2),(length − 1).
You will use the completed version of this class that is included in the starter code for lab # 8.
Assignment № 8 Page 1
Using Arrays of Integers in Ascending Order
Sample Size (N) Binary Linear
25000 ? ?
50000 ? ?
75000 ? ?
100000 ? ?
125000 ? ?
150000 ? ?
175000 ? ?
200000 ? ?
Table 1: Times To Search for a Random Key in Seconds
The Searcher Class
This class will contain your implementations for the linear and binary search algorithms. It will
contain only these methods:
1. public static int linearSearch(Integer[] data, Integer searchKey): finds a search key, the
target key, in the specified integer array using the linear search algorithm.
2. public static int binarySearch(Integer[] data, Integer searchKey): finds a search key, the
target key, in the specified integer array using the binary search algorithm.
Modify the implementations of both methods from BJLO 14.6 so that the parameters are of types
Integer[] and Integer rather than int[] and int.
SearcherDemo
Implement a class SearcherDemo, the main class of the program. This class will consist of only
one method, the main method. Your program should generate a table similar to the one shown
in table 1. (The question marks in the table represent run times in seconds to find 20000 randomly generated search keys for the array with the specified number of integers in ascending
order. Display the run times to the nearest hundred thousandths - five decimal places)
Write your main method to manage memory efficiently. Retain only one data array in memory at a time. Reuse the same data array reference any time you need an array of a different
size. (You should not hold 16 data arrays in memory at the same time.)
Assignment № 8 Page 2
Here is a pseudocode suggestion on how you could structure your main method using a
nested loop:
Listing 1: Suggested Code Structure
1 -Create two clocks, for binary and linear searches
2 for arraySize = 25000 to 200000 StepSize:=25000
3 {
4 -create an array in ascending order with the specifed size
5 -reset the clocks
6 for iteration=1 to 20000 StepSize:=1
7 {
8 - generate a random searchKey between arraySize/2
9 and 3xarraySize/2
10 - start binary clock
11 - perform binary search for the searchKey in the array
12 - stop the binary clock
13 - start linear clock
14 - perform linear search for the searchKey in the array
15 - stop the linear clock
16 }
17 - Print the array size, the elapsed time for the binary clock
18 divided by 1000.0 and the elapsed time of the linear clock
19 divided by 1000.0 are a row of the table.
20 }
In order to generate a random integer i such that m ≤ i ≤ n, the standard Java random number
generator is called as follows:
i = generator.nextInt(m-n)+n;
Additional Requirements
Write header comments, where missing, for each class using the following Javadoc documentation:
/**
* Explain the purpose of this class; what it does <br
* CSC 1350 Lab # 7
* @author YOUR NAME
* @since DATE THE CLASS WAS WRITTEN
* @version 1
*/
Assignment № 8 Page 3
For the Searcher class, after the @since line, add the following Javadoc:
* @see ArrayUtil
For the SearcherDemo class, after the @since line, add the following Javadoc:
* @see ArrayUtil, Searcher, StopWatch
Add Javadoc style documentation for each method, where missing, except for the main method.
Run the Javadoc utility to make sure that it generates documentation for all classes and methods.
After your program runs, enter the data in the excel spreadsheet template provided along
with the starter code. Save the spreadsheet and then observe the chart/graph. Answer these
questions and save your responses in a text file called README.txt.
1. Is linear search really linear when a few outliers are ignored?
2. Which algorithm seems to consistent outperform the other?
Locate your source files, ArrayUtil.java, StopWatch.java, Searcher.java and SearcherDemo.java.
Also, locate the spreadsheet in which you have entered the run times that your program generated and the files containing responses to questions that you have been asked to answer,
README.txt. Enclose your source files, spreadsheet and README.txt files in a zip file, YOURPAWSID_lab08.zip, and submit your lab assignment for grading using the digital dropbox set up
for this purpose.
Assignment № 8 Page 4