Data Abstraction and Problem Solving with C++
Walls and Mirrors
by Frank M. Carrano
c02p098.cpp
Go to the documentation of this file.00001 00029 int binarySearch(const int anArray[], int first, 00030 int last, int value) 00031 { 00032 int index; 00033 if (first > last) 00034 index = -1; // value not in original array 00035 00036 else 00037 { // Invariant: If value is in anArray, 00038 // anArray[first] <= value <= anArray[last] 00039 int mid = (first + last)/2; 00040 if (value == anArray[mid]) 00041 index = mid; // value found at anArray[mid] 00042 00043 else if (value < anArray[mid]) 00044 // point X 00045 index = binarySearch(anArray, first, mid-1, value); 00046 00047 else 00048 // point Y 00049 index = binarySearch(anArray, mid+1, last, value); 00050 } // end if 00051 return index; 00052 } // end binarySearch
