AN ITERATIVE BINARY-SEARCH ALGORITHM

In this lab, you will convert the recursive version of the binary search algorithm to an iterative algorithm.

Recursive Version of binarySearch Method

We noted at the beginning of Chapter 5 that any recursive method could be converted to an iterative method. For some of the methods in that chapter, the conversion can be quite difficult. But as you will soon discover, converting the recursive version of the binary search method into an iterative version is fairly straightforward.

For quick reference, here is the recursive version:

/**
 *  Returns an int indicating where (whether) an element searched for
 *  between two indexes in an array was found or not.  The worstTime(n) is 
 *  O(log n).
 * 
 * @param a - an array of references of type Object in which key will be 
 *            searched for.
 * @param low an int that is the low index of the area of the array 
 *            currently being searched.
 * @param high an int that is the high index of the area of the array
 *             currently being searched.
 * @param key a reference of type Object being searched for within the  
 *            array a.
 * 
 * @return an int representing either A)the element being searched for 
 *         was found and its index is returned. Or, B) the element being 
 *         searched for was not found and the -insertionPoint -1 is returned.  
 *         The insertionPoint is where the element being searched for could 
 *         be added without disordering the array.
 **/
public static int binarySearch(Object[] a, int low, int high, Object key)
{  
  if (low <= high) 
  {  
    int mid = (low + high) / 2;
    Comparable midVal = (Comparable)a [mid];
    int comp = midVal.compareTo (key);
    if (comp < 0)
      return binarySearch (a, mid + 1, high, key);
    if (comp > 0)
      return binarySearch (a, low, mid - 1, key);
    return mid;  // key found
  } // if low <= high
  return -low - 1; // key not found; belongs at a [low]  
} // method binarySearch