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.)
computer science
Description
Consider the following binary search code:
/**
* 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. }
- 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.
- 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.)
- Write test cases.
- Modify the binarySearch function in BinarySearch.hpp.
- Commit your modified code along with a script or makefile to run your tests.
