CSCI 200 - Summer 2023
Foundational Programming Concepts & Design

This lab is due by Thursday, May 04, 2023, 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.

Instructions

We will now see the benefit of all our sorting work. Add to your abstract List class a purely virtual int search(T) method. This function will need to be implemented as both int Array::search(T) and int LinkedList::search(T). The Array implementation will perform the interative binary search. The LinkedList implementation will perform the iterative linear search.

To get started, prompt the user for which list implementation they wish to use. Then ask them to enter the number of integers to store in a list. Generate n random integers and add them to your list. Finally, sort the list into ascending order.

Now we'll have the user give us a target value to search for.

To test your implementations, perform the following steps:

1. Ask the user which list implementation to use
2. Ask the user how many integers to enter n
3. Ask the user for the smallest value to generate min
4. Ask the user for the largest value to generate max
5. Create a list of n integers
6. Assign each element a random value within the range provided [min, max]
7. Print the list forwards
8. Sort the list ascending
9. Print the list forwards
10. Ask the user how many target values they wish to search for
11. For each target value entered by the user, perform an iterative binary search to find the target. If the target is found, then print the position the target is first found at. If the target is not found, then print -1.

For example, if our sorted array contains 1 3 3 3 5 and the user is searching for

• 1, then the value is found at position 0
• 3, then the value is found at position 2
• 5, then the value is found at position 4
• 2, then the value is "found" at position -1

For example, if our sorted linked list contains 1 3 3 3 5 and the user is searching for

• 1, then the value is found at position 0
• 3, then the value is found at position 1
• 5, then the value is found at position 4
• 2, then the value is "found" at position -1

Lab Submission

Submit your main.cpp, Makefile, List.hpp, Array.hpp, LinkedList.hpp file(s).

You will submit your solution to this lab with the rest of Set6. Detailed instructions for doing this are posted in Assignment 6.

This lab is due by Thursday, May 04, 2023, 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.