Searching

Learning Objective(s)

1. Implement a number of different searches
2. Start to understand Big O

Overview of the program

Details

• You are to use integers for the numbers being searched and being searched for
• The naming of your methods is very important.
• Allow for up to 10,000,000 items in each array
• You may only instantiate two arrays and each array only once. You can reuse the arrays but not re-"new" them.
• Write one method that is sent an instantiated array and a size and a range (low and high) and it should fill that array with size random numbers that range from low to high
• Write another method that is sent an instantiated array and a size and a range (low and high) and it should fill that array with size random numbers that range from low to high. The numbers need to be in order. The best way to achieve this is to start at low and add a random number(between 0 and 3) each time.
• Implement the sequential search on unordered data
• Implement the sequential search on ordered data
• Implement the binary search (using iteration) on ordered data.
• Implement the binary search (using recursion) on ordered data.
• Test your code and make sure it works using 10 elements.
  • generate random data to be search (10 elements)
  • generate random data to be searched for (10 elements) using the same range
  • search to see if each element in the second list is in the first list.
  • don't proceed until you know this works and you can explain why you know it works. (This will go in the testing report).
• Repeat those four steps but use ordered data for the items to be searched and used the sequential search on ordered data.
• Repeat again with a binary search using iteration
• Repeat again with a binary search using recursion
• Do not proceed until you know all are correct. I recommend that you implement each as a method that is sent the size, two arrays, and range.
• Add timing instructions (as covered in class) and time each of these.
• Run it with different sizes (including VERY large data sets).
• The program should be called Searching
• Output should have the size of the data being searched, the number of items searched for and how long it took
• There is no input for this program

Submission

1. Create an empty zip folder.
2. Place your program (.java file) in it
3. In Lessons Learned, you need to include a line chart plotting your times. The attached file has an example. It does NOT contain real data. You should also discuss the results * linegraph.pdf: An example of a line graph with some labels
4. Place your software development report in it.
5. Submit the zip folder on canvas

Optional improvements

• Only have one method to generate the numbers. Send it what type of data to generate (random or ordered) and only have one loop in that method to generate the data.
• Reuse the generated ordered data for all three of the ordered searches for a given size. Reuse the data being searched for in all of the searches.