Recursive Binary Search That Skips the Last Candidate
Ms. Rivera's AP Computer Science class is debugging a recursive binary-search method for a sorted array of 12 integers. The method should return the index of a target or -1. It passes tests when the target is 42 at index 6 and 17 at index 3. It returns -1 for the target 12 at index 1 and for 99 at index 11. The code begins with if (low >= high) return -1;, then computes mid = (low + high) / 2. If a[mid] == target, it returns mid; if a[mid] < target, it calls search(a, mid + 1, high, target); otherwise it calls search(a, low, mid - 1, target). The initial call is search(a, 0, a.length - 1, target). Students disagree about whether the bug is the base case, the midpoint calculation, or the recursive bounds. The teacher asks them to trace the failing calls before changing code.
1. Trace the calls for target 12 at index 1 and explain why the method returns -1. Then state the smallest code change that fixes both failing cases.
Read the worked answer
Trace for target 12 at index 1: call search(0,11); mid=5; because a[5] > 12, high becomes 4; mid=2; a[2] > 12, so high=1; mid=0; a[0] < 12, so low=1; the next call is search(1,1). The first line if (low >= high) return -1; is true, so it returns -1 without comparing a[1]. For target 99 at index 11, the range shrinks to search(11,11) and the same premature return happens. The midpoint and bound updates are consistent with an inclusive high; the defect is the base case. Change it to if (low > high) return -1; so a one-element range is still checked. Alternatively, handle low == high by returning low only if a[low] == target, else -1. With the fix, search(1,1) checks a[1], and search(11,11) checks a[11]. The invariant is that the target, if present, is always in [low, high] before the base-case test.
2. The teacher wants a test plan that would have caught this defect. Give at least five specific test cases and the expected result for each, including one absent target and one duplicate.
Read the worked answer
Specific cases: (1) target equal to the first element, expect index 0; (2) target equal to the last element, expect index 11; (3) target equal to the second element, expect index 1, which is the case that failed; (4) target smaller than every element, expect -1; (5) target between two elements but absent, expect -1; (6) duplicate target, define the expected result as any valid index or the first index depending on the specification. Also test array length 1, an empty array, and both even and odd lengths. For each case, state the expected index and why the boundary matters. Include an explicit trace or assertion for the one-element case because the old base case fails it. This test set exercises low == high, low > high, equality at mid, and absence, so it would have exposed the defect before the code was accepted.