Previous Section
 < Free Open Study > 
Next Section


7.8 A Recursive Version of Binary Search

In the chapter on array-based lists (Chapter 3), we developed a binary search algorithm for the member function RetrieveItem in our Sorted List ADT. Let's review the algorithm:

Although the function that we wrote in Chapter 3 was iterative, this really is a recursive algorithm. The solution is expressed in smaller versions of the original problem: If the answer isn't found in the middle position, perform BinarySearch (a recursive call) to search the appropriate half of the list (a smaller problem). Let's summarize the problem in terms of a Boolean function that simply returns true or false to indicate whether the desired item is found. We assume that it is not a public member function of the class ListType but rather an auxiliary function of the class that takes the array info as a parameter.

The recursive version of the function follows. Because each branch of the switch statement includes only one statement, we use the relational operators. Notice that we had to make fromLocation and toLocation become parameters to the function rather than local index variables. An initial call to the function would be of the form Binary - Search(info, item, 0, length - 1).

template<class ItemType>
bool BinarySearch(ItemType info[], ItemType item,
                  int fromLocation, int toLocation)
{
  if (fromLocation > toLocation)          // Base case 1
    return false;
  else
  {
    int midPoint;
    midPoint = (fromLocation + toLocation) / 2;
    if (item < info[midPoint])
      return
        BinarySearch(info, item, fromLocation, midPoint - 1);
    else if (item == info[midPoint])
      return true;
    else                                  // Base case 2
      return
        BinarySearch(info, item, midPoint + 1, toLocation);
  }
}



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)