Programming Puzzles: Python Edition

Background

Binary search is an efficient algorithm for finding an item from a sorted list of items. The basic idea behind the algorithm is to repeatedly divide the search interval in half until the value is found, or the search interval is empty.

To carry out a binary search the following steps can be executed:

1. Set the search interval equal to the whole list.
2. Calculate the middle element. If the length of the list is even, we take the lower middle element e.g. for [1, 2, 3, 4] we would say the middle element is 2.
3. The middle element of the search interval is compared to the value we are searching for, then:
   1. If the middle element is equal to the value we are searching for, the algorithm stops and returns the index of the element.
   2. If the middle ...