Lab 19.2 Search
Background
You will need to have completed Lab 19.1 Store to complete this assignment. Your task will be to add the binary search algorithms presented below to your Store class. You should use the following testing method in your solution.
public void testSearch(){
int idToFind;
int invReturn;
int index;
Scanner in = new Scanner(System.in);
System.out.println("Testing search algorithm\n");
do{
System.out.println();
System.out.print("Enter Id value to search for (-1 to quit) ---> ");
idToFind = in.nextInt();
//index = bsearch(new Item(idToFind, 0));
//recursive version call
index = bsearch (new Item(idToFind, 0), 0, myStore.size()-1);
System.out.print("Id # " + idToFind);
if (index == -1){
System.out.println(" No such part in stock");
}else{
System.out.println(" Inventory = " + myStore.get(index).getInv());
}
} while (idToFind >= 0);
}
/**
* Searches the myStore ArrayList of Item Objects for the specified
* item object using a iterative binary search algorithm
*
* @param idToSearch Item object containing id value being searched for
* @return index of Item if found, -1 if not found
*/
private int bsearch(Item idToSearch){
return -1;
}
/**
* Searches the specified ArrayList of Item Objects for the specified
* id using a recursive binary search algorithm
*
* @param idToSearch Id value being search for
* @param first Starting index of search range
* @param last Ending index of search range
* @return index of Item if found, -1 if not found
*/
private int bsearch(Item idToSearch, int first, int last){
return -1;
}
Assignment
Add the above code to your Store.java class.
Complete both of the binary search methods, iterative and recursive.
An example output is given below.
Id # 15320 Inventory = 82
Id # 196 Inventory = 60
Id # 19967 Inventory = 45
Id # 2 No such part in stock
Id # 20000 No such part in stock
Put all three files (Item, Store, Driver) in a single file as you did for Lab 19.1 and upload it below.
Test Cases
You are responsible for testing each of the cases below to make sure your code works properly.
- Search for an item BEYOND the end of the list
- Search for an item BEFORE the start of the list
- Search for the FIRST item
- Search for the LAST item
- Search for an item that would be somewhere between the FIRST and LAST but is NOT in the list
- Search for a few random items that ARE in the list
- Search for the exact middle item
- Search for the second to last item
- Search for the second item
You must Sign In to submit to this assignment
Tino APCS