Binary Search

The binary search is used to find an item in an ORDERED list.

For example, we want to find a number in the list below:

1
2, 5, 7, 12, 14, 21, 28, 31, 36

To search for an item, look in the middle of the list and see if the number you want is in the middle, above the middle or below the middle. If it is in the middle, you have found the item. If it is higher than the middle value, then adjust the bottom of the list so that you search in a smaller list starting one above the middle of the list. If the number is lower than the middle value, then adjust the top of the list so that you search in a smaller list which has its highest position one less than the middle position.

The algorithm is as follows (given a list called 'List' and looking for an item called 'item'):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
Found <- False
while not Found and first <= top
    Midpoint <- (First + Last) DIV 2
    If List[Midpoint] = ItemSought Then
        ItemFound <- True
    Else
        If First >= Last Then
            SearchFailed <- True
        Else
            If List[Midpoint] > ItemSought Then
                Last <- Midpoint - 1
            Else
                First <- Midpoint + 1
            EndIf
        EndIf
    EndIf

This video clip shows how to write a binary search in Python:


Exercises

  1. Implement the binary search as described in the video and using the algorithm. Test that it works with items in and not in the list
  2. Add a counter to report how many searches have been done for each item searched for