Binary Search

Write a program binary_search.py that:

1. begins with the sorted list l = [1, 2, 3, 4, 7, 9, 13, 14, 20]
2. identifies a search term (key = 4, for example)
3. calls a function search() that performs a Binary Search for that item in your list. That function will use a loop to examine successively smaller search spaces in the list.
4. The function should return the index of the item, or a value of None if the item is not on the list.
5. The main program should print the location (index) of the search item, if it exists. Otherwise, print out a "search item not found" message.

You will certainly find it handy to include some print() statements to reveal the progress of your search as it goes.

Test your program with the following lists to see if it works. When testing your program, be sure to look for an item that is on the list, and also an item that isn't on the list.

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