File IntegerListS.java contains a class IntegerListS that represents a list of integers (you may have used a version of this in an earlier lab); IntegerListSTest.java contains a simple menu-driven test program that lets the user create, sort, and print a list and search for an element using a linear search.

Many list processing tasks, including searching, can be done recursively. The base case typically involves doing something with a limited number of elements in the list (say the first element), then the recursive step involves doing the task on the rest of the list. Think about how linear search can be viewed recursively; if you are looking for an item in a list starting at index i:

- If i exceeds the last index in the list, the item is not found (return -1).

- If the item is at list[i], return i.

- If the is not at list[i], do a linear search starting at index i+1.

Fill in the body of the method linearSearchR in the IntegerList class. The method should do a recursive linear search of a list starting with a given index (parameter lo). Note that the IntegerList class contains another method linearSearchRec that does nothing but call your method (linearSearchR). This is done because the recursive method (linearSearchR) needs more information (the index to start at) than you want to pass to the top-level search routine (linearSearchRec), which just needs the thing to look for.

Now change IntegerListTest.java so that it calls linearSearchRec instead of linearSearch when the user asks for a linear search. Thoroughly test the program.

// *************************************************************** // IntegerListS.java // // Defines an IntegerListS class with methods to create, fill, // sort, and search in a list of integers. (Version S - // for use in the linear search exercise.) // // *************************************************************** public class IntegerListS { int[] list; //values in the list // ------------------------------------ // Creates a list of the given size // ------------------------------------ public IntegerListS (int size) { list = new int[size]; } // ------------------------------------------------------------- // Fills the array with integers between 1 and 100, inclusive // ------------------------------------------------------------- public void randomize() { for (int i=0; i< list.length; i++) list[i] = (int)(Math.random() * 100) + 1; } // ---------------------------------------- // Prints array elements with indices // ---------------------------------------- public void print() { for (int i=0; i

// ****************************************************************

// IntegerListSTest.java

//

// Provide a menu-driven tester for the IntegerList class.

// (Version S - for use in the linear search lab exercise).

//

// ****************************************************************

import java.util.Scanner;

public class IntegerListTest

{

static IntegerList list = new IntegerList(10);

static Scanner scan = new Scanner(System.in);

// ------------------------------------------------------------------

// Creates a list, then repeatedly print the menu and do what the

// user asks until they quit.

// ------------------------------------------------------------------

public static void main(String[] args)

{

printMenu();

int choice = scan.nextInt();

while (choice != 0)

{

dispatch(choice);

printMenu();

choice = scan.nextInt();

}

}

// -------------------------------------

// Does what the menu item calls for.

// -------------------------------------

public static void dispatch(int choice)

{

int loc;

switch(choice)

{

case 0:

System.out.println("Bye!");

break;

case 1:

System.out.println("How big should the list be?");

int size = scan.nextInt();

list = new IntegerListS(size);

list.randomize();

break;

case 2:

list.selectionSort();

break;

case 3:

System.out.print("Enter the value to look for: ");

loc = list.linearSearch(scan.nextInt());

if (loc != -1)

System.out.println("Found at location " + loc);

else

System.out.println("Not in list");

break;

case 4:

list.print();

break;

//add case 5 and 6 and 7

default:

System.out.println("Sorry, invalid choice");

}

}

// -------------------------------------

// Prints the menu of user's choices.

// -------------------------------------

public static void printMenu()

{

System.out.println(" Menu ");

System.out.println(" ====");

System.out.println("0: Quit");

System.out.println("1: Create new list elements (** do this first!! **)");

System.out.println("2: Sort the list using selection sort");

System.out.println("3: Find an element in the list using linear search");

System.out.println("4: Print the list");

System.out.print(" Enter your choice: ");

}

}