Consider the following method, which implements a recursive binary search.

/** Returns an index in theList where target appears,

* if target appears in theList between the elements at indices

* low and high, inclusive; otherwise returns -1.

* Precondition: theList is sorted in ascending order.

* low >= 0, high < theList.size(), theList.size() > 0

*/

public static int binarySearch(ArrayList theList, int low, int high,

int target)

{

if (low > high)

{

return -1;

}

int middle = (low + high) / 2;

if (target == theList.get(middle))

{

return middle;

}

else if (target < theList.get(middle))

{

return binarySearch(theList, low, middle - 1, target);

}

else

{

return binarySearch(theList, middle + 1, high, target);

}

}

The following code segment appears in a method in the same class as binarySearch.

ArrayList theList = new ArrayList();

for (int k = 10; k < 65; k = k + 5)

{

theList.add(k);

}

int result = binarySearch(theList, 0, theList.size() - 1, 45);

Including the call to binarySearch in the last statement of the given code segment, how many times will binarySearch be called before a value is returned?

• A. 1

• B. 2

• C. 3

• D. 4

• E. 8