Binary search

Binary search is a common, efficient method to search in sorted lists. The binary search method already came up earlier in the course, but was not named as such.

Guessing game

One place where binary search was brought up, was in programming a guessing game. This game works as follows: One player picks a number between 1 and 1000, and the other player tries to guess it. After each number that the second player guesses, the first player says whether the number that he picked is lower, higher, or equal to the guessed number.

A method to guess the number is by starting at 1, and then increasing by 1 after every guess. This method is O(n), as it emulates linear search. However, since the number is picked from a sorted list (it is sorted because the first player can say “lower” or “higher” after every guess), it is possible to identify the target number more efficiently. You probably see how, but I will make it explicit:

Suppose that the first player picked 278. The second player first divides the range of numbers 1-1000 into two ranges and one number that is between the ranges, namely: 1-499, 500, and 501-1000. The single number in the middle is used as guess, i.e., 500. The first player says that the target is “lower”. This means that now the range of numbers that needs to be searched is 1-499.

The second player then divides the remaining range again into two (almost) equal parts, and the middle number: 1-249, 250, and 251-499. The guess is 250, and the second player learns that the target is “higher”. So now the range to search is 251-499, which is less than a quarter of the original range, after only two guesses.

The guessing continues, each guess dividing the range to search into half of what it was previously. By the time the length of the range is 1, the number has been guessed. This happens in the worst case after log₂(n)+1 guesses, whereby n is the size of the original range. For 1000 numbers, this is 10 guesses at most.

Note that it does not matter whether a list is used where the distance between each following two items is a constant. When I say that you pick the middle, that means you pick the item with the middle index.

Binary search implementation

The method described above, whereby you divide the range to search in two halves after every trial, is called “binary search”. It is O(log(n)) and Ω(1).

A common implementation of binary search retains the lower and the higher index for the range which is searched. For every trial, the middle of these two indices is calculated and checked. On the basis of this check, either the value for the middle will be returned, or either the lower index or the higher index will be set to the middle plus 1 or minus 1, respectively. Typical code is shown below:

# This implementation of binary search returns the index of the target in tlist.
# If target is not found in the list, it returns -1.
def binary_search( tlist, target ):
    lo = 0
    hi = len( tlist )-1
    while lo <= hi:
        mid = lo + (hi-lo)//2
        if tlist[mid] == target:
            return mid            
        elif tlist[mid] < target: 
            lo = mid+1
        else:
            hi = mid-1
    return -1

numlist = [-4, -2, -1, 1, 5, 8, 11, 12, 15, 16, 22, 35, 37, 39, 40, 50, 60, 72, 88, 91, 92, 93, 95]
for i in range( 10 ):
    index = binary_search( numlist, i )
    if index >= 0:
        print( "Index of value", i, "in the list is", index )
    else:
        print( "Value", i, "is not in the list" )