/**
         * Performs the standard binary search using two comparisons per level.
         * Returns index where item is found or -1 if not found.
         */
         1.  template <typename Comparable>
         2.  int binarySearch( const vector <Comparable> & a, const Comparable & x )
         3.  {
         4.      int low=0;
         5.      int high= a.size( ) - 1;
         6.
         7.      while( low <= high ) {
         8.         int mid=(low + high ) / 2;
         9.         if( a[mid]<x) {
         10.            low = mid+ 1;
         11.        } else if( a[ mid ]>x) {
         12.            high = mid - 1;
         13.        } else {
         14.          return mid;
         15.       }
         16.    }
         17.    return NOT_FOUND;  // NOT_FOUND defined as -1
         18.  }
  

1. Suppose line 10 above was low = mid instead of low = mid + 1. Would the routine still work? If so, explain why. If not, give an input that fails.
2. Rewrite the algorithm above so that there is only one comparison per loop iteration. (Specifically, the body of the while loop may contain only one comparison.)
   • Follow this GitHub Classroom invitation link to setup your project: classroom.github.com/a/oHQ_9hQY
   • Write test cases.
   • Modify the binarySearch function in BinarySearch.hpp.
   • Commit your modified code along with a script or makefile to run your tests.

Submission and grading

Please submit a hard copy of question 1 above. Use GitHub classroom to submit the answer to question 2.

(Note: Exercises above drawn largely from the Weis text.)

Updated Wednesday, 28 August 2019, 11:14 AM