Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Searching and Recursion
The goal of this week’s lab is:
1. Practice searching
2. Continue learning the significance of special cases!
3. Learning how to write test to check your implementation
Things you must do:
1. There are many details in this lab. Make sure you read the whole thing carefully
before writing any code and closely follow this instruction.
2. Always remember Java is case sensitive.
3. Your file names, class names, and package name must match exactly as
they are specified here.
Things you must not do:
1. You must not change the file names, class names, package names.
2. You must not change the signature of any of these methods (name, parameters,
…). Just fill in the missing code inside them. However, you are more than welcome
to create any helper methods you need as necessary.
Part 0
? Create a new Java project and call it Lab05.
? Create a package inside your project and call it lab05.
? Download the Lab05-Assignment05 ZIP folder from Google Drive (link from
blackboard assignment). Copy and paste the following files into your new
lab05 package:
? SortedBinarySet.java. This file will contain the representation of the class
you are about to implement.
? Tester.java. This file will contain the main function and tests for
SortedBinarySet.
Part 1 - SortedBinarySet Class Description
For this lab (and assignment), you are asked to construct a class called
SortedBinarySet that handles a list(s) of doubles. We have provided the skeleton of
this class for you. This class requires:
? All of the usual operations for a list, such as the ability to add items, remove
items, search for items, grow itself before running out of space.
? You must make your search routine(s) as efficient as possible. You are not
allowed to use sort algorithms. Instead, you need to consider the fact that
any list will begin as an empty list (which is already in sorted order), and you
can simply insert items in the correct order to ensure that the list remains sorted
at all times.
? Furthermore, the list must not contain any duplicates. (Because it’s a “set”)
? The data in SortedBinarySet must be backed by a basic array (do not use a
Java List, ArrayList, or any other Java class).
? It is not acceptable for the array to run out of space for new items, nor is it
acceptable to create a gigantic array. We will start with a modestly-sized array,
say size 11, and increase the capacity as needed (see the grow() function
description).
? Unlike previous assignments you are not given any tests as a starting point.
You must create your own tests and submit them with your program. (Note
that the previous assignment will be very useful in helping you accomplish
this).
Part 2 – SortedBinarySet Class Implementation
We start by implementing the easier methods. Remember that the list must be
sorted at all times. Please pay close attention to the following notes:
● public SortedBinarySet() // default constructor
○ This constructor must initialize an array of size 11 (hint: use the final
variable INITIAL_STORAGE_CAPACITY)
○ and set the rest of the field members accordingly. Pay attention to the
member variables of the class! Each should be set to some
(appropriate) initial value.