Binary Search

Write a program binary_search.py that

1. begins with a sorted list lst = [1, 2, 3, 4, 7, 9, 13, 14, 20]
2. identifies a search value (key = 3, for example)
3. calls a function search(lst) 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 (location) of the item in the list, or a -1 if not found.
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                  -1
[1, 2, 3, 4, 7, 9, 13, 14, 20]      23                  -1
[1, 2, 3, 4, 7, 9, 13, 14, 20]      10                  -1
[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                   -1
[4, 7, 9, 13, 14, 20]               10                  -1
[4, 7, 9, 13, 14, 20]               22                  -1