Algorithms For Dummies

  Performing Essential Data Manipulations Using Python 

     109

def search(searchList, key):

    mid = int(len(searchList) / 2)

    print("Searching midpoint at ", str(searchList[mid]))

  

    if mid == 0:

        print("Key Not Found!")

        return key

  

    elif key == searchList[mid]:

        print("Key Found!")

        return searchList[mid]

  

    elif key > searchList[mid]:

        print("searchList now contains ",

              searchList[mid:len(searchList)])

        search(searchList[mid:len(searchList)], key)

  

    else:

        print("searchList now contains ",

              searchList[0:mid])

        search(searchList[0:mid], key)

  

aList = list(range(1, 21))

search(aList, 5)

  

Searching midpoint at  11

searchList now contains  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Searching midpoint at  6

searchList now contains  [1, 2, 3, 4, 5]

Searching midpoint at  3

searchList now contains  [3, 4, 5]

Searching midpoint at  4

searchList now contains  [4, 5]

Searching midpoint at  5

Key Found!

This  recursive  approach  to  the  binary  search  begins  with 

aList

  containing  the 

numbers 1 through 20. It searches for a value of 

5

 in 

aList

. Each iteration of the 

recursion begins by looking for the list’s midpoint, 

mid

, and then using that mid-

point to determine the next step. When the 

key

 matches the midpoint, the value 

is found in the list and the recursion ends.

---

110