Lab 12: Searching
Due Date and Submission Requirements
- Due Date: Tuesday, April 22nd at 11:59 p.m.
- Partner Information: This is an individual assignment. You are allowed to collaborate with other students, but each student must submit their individual, independent solution.
- Submission Instructions: Submit your Lab12Demo.java file to the appropriate D2L dropbox.
The goal of this lab is:
- Understand how Binary Search works, and compare against a linear search.
Directions
For this assignment, you will be comparing binary search and linear search. You will keep track of the time it takes for each algorithm to complete (in milliseconds), and the amound of array spots that are checked during each algorithm. Using Lab12Demo.java as a starting point, you will fill in the methods for linear_search() and binary_search(). You will also need to write some code to complete the main() method.
You will compare binary search and linear search for an array size of 50, 500, 5000, and 50000. You can use the method getRandomArray() to fill the contents of these arrays. You will select a random index, and then search for that element with the two different algorithms. You will need to keep track of how many array spots are checked, and the running time in milliseconds (we talked about how to do that in class). Remember to sort your array before binary search (but the running time should not include the time it takes to sort).
Then, you must print out the results (see sample output).
Starting Code
Output
When you run your program, your output should look something like this: sample output. Your values will definitely be different that my sample output, but you should find that binary search checks a lot less array spots, and has a shorter running time.
Grading (10 points)
- 3 points- Binary search is implemented correctly
- 2 points- Linear search is implemented correctly
- 3 points- Your program keeps track of array spots checked
- 2 points- Your program keeps track of running time in ms