CSE 1302 J

Fall 2014

Lab 8

 

 

Recursion in array handling

              

           

         Iterative Linear Search (given)

         Recursive Linear Search

         Add recursive linear search logic to linearSearchR

         Make case 5 in main a call linearSearchRec.

         Iterative Binary Search

         Add a new method to your IntegerList, called intbinarySearch (int target) which will binary search the array iteratively

         Make case 6 in main a call to binarySearch

         Recursive Binary Search

         Add recursive logic to binarySearchR

         Make case 7 in main a call binarySearchRec

 

Turn in the final source and output that does the following:

         Create an array of 10 positions and print it.

         Search for first item, last item, a middle item in the list, and an item not in list, using linear search, iterative version, case 3

         Search for first item, last item, a middle item in the list, and an item not in list, using linear search, recursive version, case 5

         Now sort the array and print it.

         Search for first item, last item, a middle item in the list, and an item not in list, using binary search, iterative version, case 6

         Search for first item, last item, middle item in the list, and an item not in list, using binary search, recursive version, case 7

 

Recursive Linear Search

 

File IntegerList.java contains a class IntegerList that represents a list of integers (you may have used a version of this in an earlier lab); IntegerListTest.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 iexceeds 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.

 

 

 

 

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

//   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;

    }

 

    • 9 years ago
    Complete A++ Solution
    NOT RATED

    Purchase the answer to view it

    blurred-text
    • attachment
      lab_8_recursion_answer.zip