binarysearch.cpp

Data Abstraction & Problem Solving with C++源码

int binarySearch(const int anArray[], int first,
                 int last, int value)
// ---------------------------------------------------------
// Searches the array items anArray[first] through
// anArray[last] for value by using a binary search.
// Precondition: 0 <= first, last <= SIZE-1, where
// SIZE is the maximum size of the array, and
// anArray[first] <= anArray[first+1] <= ... <=
// anArray[last].
// Postcondition: If value is in the array, the function
// returns the index of the array item that equals value;
// otherwise the function returns -1.
// ---------------------------------------------------------
{
   int index;
   if (first > last)
      index = -1;      // value not in original array
   else
   {  // Invariant: If value is in anArray,
      //            anArray[first] <= value <= anArray[last]
      int mid = (first + last)/2;
      if (value == anArray[mid])
         index = mid;  // value found at anArray[mid]

      else if (value < anArray[mid])
         // point X
         index = binarySearch(anArray, first, mid-1, value);

      else
         // point Y
         index = binarySearch(anArray, mid+1, last, value);
   }  // end else
   return index;
}  // end binarySearch