public static int binarySearch(int[] a, int x, int low, int high) { if (low > high) { return -1; // x can't be in an invalid range } int index = (low+high)/2; int y = a[index]; if (x == y) { return index; } else if (x < y) { return binarySearch(a, x, low, index-1); } else { // x > y return binarySearch(a, x, index+1, high); } } 

We tested it against a linear search implementation that we saw in class earlier. The code starts by creating an array of a million monotonically increasing values (a subsequent value can differ from its predecessor by 0, 1, or 2). Then, it times searching for 100000 values in that array. We also add up all the indexes where we find what we're looking for along with -1 values when we don't find what we're looking for. Finally, we search for the same values with binarySearch and also add either the found index or -1 if not found.

 int[] a = new int[1000000]; for (int i = 1; i < a.length; i++) { a[i] = a[i-1] + (int)(Math.random()*3); } long start = System.currentTimeMillis(); long indexSum = 0; int maxSearch = 100000; for (int x = 0; x < maxSearch; x++) { for (int j = 0; j < a.length; j++) { if (a[j] == x) {indexSum += j; break;} // We found it else if (a[j] > x) {indexSum -= 1; break;} // We will never find it } } long end = System.currentTimeMillis(); System.out.println(end-start); long indexSum2 = 0; start = System.currentTimeMillis(); for (int x = 0; x < maxSearch; x++) { indexSum2 += binarySearch(a, x); } end = System.currentTimeMillis(); System.out.println(end-start); System.out.println(indexSum+" "+indexSum2); 

However, we saw that the indexSum values differed. They don't differ by much, though! Which of these changes to binarySearch will fix it?

A. For the x < y case, instead, return binarySearch(a, x, low, index);

B. For the x > y case, instead, return binarySearch(a, x, index, high);

C. Instead of if (low > high), change to if (low >= high)

D.	For the x == y case, before return index, if (index > low) return binarySearch(a, x, low, index);