Write a class BinarySearcherRecursive has a recursive
method search that will perform a recursive binary search
for a given item on a list.
Try writing it without any hints before looking at the information below.
Because we need to keep track of the lower and upper bounds of our
search area, we'll need to include those as parameters in our
search function. That way we can modify them each time we
make a recursive call.
def search(arr : list, value : int, lower : int, upper :
int)
For this strategy, both arr and value are the
same everytime the function is called, but the lower and
upper bounds of the region being examined are modified for
each recursive call.
As before, use these lists and target values to test your recursive search.
List to search Item to look for Expected result
[1, 2, 3, 4, 7, 9, 13, 14, 20] 7 4
[1, 2, 3, 4, 7, 9, 13, 14, 20] 1 0
[1, 2, 3, 4, 7, 9, 13, 14, 20] 20 8
[1, 2, 3, 4, 7, 9, 13, 14, 20] -2 None
[1, 2, 3, 4, 7, 9, 13, 14, 20] 23 None
[1, 2, 3, 4, 7, 9, 13, 14, 20] 10 None
[4, 7, 9, 13, 14, 20] 9 2
[4, 7, 9, 13, 14, 20] 13 3
[4, 7, 9, 13, 14, 20] 20 5
[4, 7, 9, 13, 14, 20] 2 None
[4, 7, 9, 13, 14, 20] 10 None
[4, 7, 9, 13, 14, 20] 22 None