INFO 206B

INFO 206B, Assignment 2. Submit your Jupyter notebook (.ipynb file) that contains your well-commented code. Please name your file that you submit {firstname_lastname}_A1.ipynb.

Implement a recursive binary search in which you search a sorted list of numbers for a specific number.
Your recursive function should take as input four parameters: a sorted list being searched, the key being searched for, and a left and right index into the list. Your fucntion looks only in the sublist starting at index left and going through and including index right. For example, suppose that the_list is:
```
[27, 78, 105, 135, 411, 431, 434, 468, 493, 501, 525, 534, 551, 654, 780]
```
which contains 15 items, indexed 0 to 14. If I call binary_search(the_list, 135, 0, 14), then I'm considering the entire list, and the return value should be 3, since the value 135 appears at index 3. If I call binary_search(the_list, 500, 0, 14), the return value should be None, since the value 500 is not in the_list. The call binary_search(the_list, 135, 2, 12) should return 3 since, as before, the value 135 appears at index 3 in the_list. Notice that the index returned is the index in the entire list, not the relative index in the sublist starting at index left. The parameters left and right just give the range of indices into the list that we're considering in a given call of binary_search.
Here's what you need to do in your binary_search function
1. If the sublist of the_list starting at index left and going up to and including index right is empty, then key cannot be in the sublist -- return None.
2. Otherwise, the sublist is not empty, and you should:
  1. Compute the midpoint of this sublist, by averaging left and right.
  2. If key is equal to the item at index midpoint of the_list, then it has been found. Return this index.
  3. Otherwise, because the_list is sorted, you can tell whether key, if in the_list, is either in the sublist before the midpoint or in the sublist after the midpoint.
  4. If key is less than the item at the midpoint and it's in the list, then it must be in the sublist before the midpoint. Recursively return the result of calling binary_search on the sublist starting at index left and going up to and including the index just before midpoint.
  5. Only one other possibility remains: key is greater than the item at the midpoint, and so if it's in the list, then it must be in the sublist after the midpoint. Recursively return the result of calling binary_search on the sublist starting at the index just after midpoint and going up to and including index right.
Once you've written your recursive binary search function, you should write a simple user interface as follows:
1. Prompt the user to specify the number N of elements in a list that you will create to be searched.
2. Generate a list of N random integers, with each integer in the range of 0 to 1000 (you can use Python's built-in function sorted to sort this list).
3. Print the list so that the user can see it.
4. Prompt the user for input from the keyboard. If the user enters "?" then print the list, if the user enters "q", then quit the entire program, otherwise search the list for the element that the user entered (you need not worry about verifying that they entered an integer -- assume that they will).
5. Repeat this entire process until the user quits.

Resources

15 sorting algorithms in 6 minutes