Tino APCS

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

  1. Add the above code to your Store.java class.

  2. Complete both of the binary search methods, iterative and recursive.

  3. 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
    
  4. 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.

  1. Search for an item BEYOND the end of the list
  2. Search for an item BEFORE the start of the list
  3. Search for the FIRST item
  4. Search for the LAST item
  5. Search for an item that would be somewhere between the FIRST and LAST but is NOT in the list
  6. Search for a few random items that ARE in the list
  7. Search for the exact middle item
  8. Search for the second to last item
  9. Search for the second item

You must Sign In to submit to this assignment

Dark Mode

Outline