•         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.

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

//   IntegerList.java

//

//   Defines an IntegerList 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 IntegerList

{

int[] list; //values in the list

    // ————————————

    //   Creates a list of the given size

    // ————————————

publicIntegerList (int size)

    {

      list = new int[size];

    }

    // ————————————————————–

    //   Fills the array with integers between 1 and 100, inclusive

    // ————————————————————–

public void randomize()

    {

      for (inti=0; i<list.length; i++)

      list[i] = (int)(Math.random() * 100) + 1;

    }

    // —————————————-

    //   Prints array elements with indices

    // —————————————-

public void print()

    {

      for (inti=0; i<list.length; i++)

      System.out.println(i + “:t” + list[i]);

    }

    // ——————————————————————

    //   Returns the index of the first occurrence of target in the list.

    //   Returns -1 if target does not appear in the list.

    // ——————————————————————

publicintlinearSearch(int target)

    {

      int location = -1;

      for (inti=0; i<list.length&& location == -1; i++)

      if (list[i] == target)

            location = i;

      return location;

    }

    // —————————————————————–

    //   Returns the index of an occurrence of target in the list, -1

    //   if target does not appear in the list.

    // —————————————————————–

publicintlinearSearchRec(int target)

    {

      returnlinearSearchR (target, 0);

    }

    // —————————————————————–

    //   Recursive implementation of the linear search – searches

    //   for target starting at index lo.

    // —————————————————————– 

privateintlinearSearchR (int target, int lo)

    {

      // fill in code for linear search recursive

      return -1;

    }

    // ——————————————————————

    //   Returns the index of the occurrence of target in the list.

    //   Returns -1 if target does not appear in the list.

    // ——————————————————————

publicintbinarySearch(int target)

    {

      // fill in code for iterative binary search

    }

// —————————————————————–

    //   Returns the index of an occurrence of target in the list, -1

    //   if target does not appear in the list.

    // —————————————————————–

publicintbinarySearchRec(int target)

    {

      returnbinarySearchR (target, 0, list.length-1);

    }

    // —————————————————————–

    //   Recursive implementation of the binary search algorithm.

    //   If the list is sorted the index of an occurrence of the

    //   target is returned (or -1 if the target is not in the list).

    // —————————————————————– 

privateintbinarySearchR (int target, int lo, int hi)

    {

      int index;

      // fill in code for the binary search recursive

      return index;

    }

    // ————————————————————————

    //  Sorts the list into ascending order using the selection sort algorithm.

    // ————————————————————————

public void selectionSort()

    {

      intminIndex;

      for (inti=0; i< list.length-1; i++)

          {

            //find smallest element in list starting at location i

            minIndex = i;

            for (int j = i+1; j <list.length; j++)

            if (list[j] < list[minIndex])

                  minIndex = j;

            //swap list[i] with smallest element

            int temp = list[i];

            list[i] = list[minIndex];

            list[minIndex] = temp;

          }

    }

}

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

//    IntegerListSTest.java

//

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

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

//         

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

importjava.util.Scanner;

public class IntegerListTest

{

staticIntegerList 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)

    {

      intloc;

      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(“n   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(“nEnter your choice: “);

    }

}

Recursive Binary Search

The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered list.  The algorithm (in pseudocode) is as follows:

highIndex – the maximum index of the part of the list being searched

lowIndex – the minimum index of the part of the list being searched

target — the item being searched for

   //look in the middle

middleIndex = (highIndex + lowIndex) / 2

if the list element at the middleIndex is the target

return the middleIndex

else

if the list element in the middle is greater than the target

search the first half of the list

else

search the second half of the list

Notice the recursive nature of the algorithm.  It is easily implemented recursively. Note that three parameters are needed—the target and the indices of the first and last elements in the part of the list to be searched. To “search the first half of the list” the algorithm must be called with the high and low index parameters representing the first half of the list. Similarly, to search the second half the algorithm must be called with the high and low index parameters representing the second half of the list. The file IntegerListB.java contains a class representing a list of integers (the same class that has been used in a few other labs); the file IntegerListBTest.java contains a simple menu-driven test program that lets the user create, sort, and print a list and search for an item in the list using a linear search or a binary search. Your job is to complete the binary search algorithm (method binarySearchR). The basic algorithm is given above but it leaves out one thing: what happens if the target is not in the list? What condition will let the program know that the target has not been found? If the low and high indices are changed each time so that the middle item is NOT examined again (see the diagram of indices below) then the list is guaranteed to shrink each time and the indices “cross”—that is, the high index becomes less than the low index. That is the condition that indicates the target was not found.

lo                 middle                     high

lo         middle-1     middle+1              high

       ^             ^            ^                    ^

       |             |            |                    |

        ————-              ——————–

first half                      last half

Fill in the blanks below, then type your code in. Remember when you test the search to first sort the list.

privateintbinarySearchR (int target, int lo, int hi)

    {

      int index;

      if (  ____________________________  ) // fill in the “not found” condition   

      index = -1;

      else

          {

            int mid = (lo + hi)/2;

            if ( ______________________________ ) // found it!

            index = mid;

            else if (target < list[mid])

                    // fill in the recursive call to search the first half

                    // of the list

            index = _______________________________________________;

            else

                    // search the last half of the list

            index = _______________________________________________;

          }

      return index;

    }