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

/** Returns an index in arr where the value str appears if str appears

* in arr between arr[left] and arr[right], inclusive;

* otherwise returns -1.

* Precondition: arr is sorted in ascending order.

* left >= 0, right < arr.length, arr.length > 0

*/

public static int bSearch(String[] arr, int left, int right, String str)

{

if (right >= left)

{

int mid = (left + right) / 2;

if (arr[mid].equals(str))

{

return mid;

}

else if (arr[mid].compareTo(str) > 0)

{

return bSearch(arr, left, mid - 1, str);

}

else

{

System.out.println("right");

return bSearch(arr, mid + 1, right, str);

}

}

return -1;

}

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

String[] words = {"arc", "bat", "cat", "dog",

"egg", "fit", "gap", "hat"};

int index = bSearch(words, 0, words.length - 1, "hat");

How many times will "right" be printed when the code segment is executed?

A. 1

B. 2

C. 3

D. 7

E. 8