Question

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. private int binarySearchR (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 238 Chapter 12: Recursion // search the last half of the list index = _______________________________________________; } return index; }

Answer 1

import java.util.Arrays;

public class IntegerListB {

   int[] list;

   public IntegerListB(int[] list) {

       this.list = list;

   }

   public int serach(int target){

       Arrays.sort(list);

       return binarySearchR(target, 0, list.length-1);

   }

   private int binarySearchR (int target, int lo, int hi) {

       int index;

       if (lo > hi){

           index = -1;

       }

       else {

           int mid = (lo + hi)/2;

           if (list[mid] == target)

               index = mid;

           else if (target < list[mid]) {

               index = binarySearchR(target, lo, mid - 1);

           }

           else index = binarySearchR(target, mid+1, hi);

       }

       return index;

   }

}