Rewrite Example 13.8, RecursiveBinarySearch, using an array sorted in descending order.

Example 13.8

We coded the recursiveBinarySearch method at lines 2752. That method takes four parameters: arr, the array we are searching; key, the value we are searching for; and start and end, which represent, respectively, the first and last index of the subarray of arr that we should search.

At line 38, we test if the subarray we are searching contains at least one element. If it does not, we have reached a base case and we know that we will not find key. Thus, we return 1 in the else clause at line 51. If the subarray has at least one element, we assign the index of the middle element of the subarray to middle at line 41. We then compare the array element at index middle to key at line 43. If they are equal, we have reached the other base case (we have found key) so we return middle at line 44.

If the array element at index middle is greater than key, we call the recursiveBinarySearch method with the subarray consisting of all elements with values lower than middle (from start to middle 1) at line 46. If the array element at index middle is smaller than key, then we call the recursiveBinarySearch method with the subarray consisting of all elements with values higher than middle (from middle + 1 to end) at line 48. In both cases, whatever is returned by the recursive call is returned by the method.