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

by Sue Sentance.
01 November 2012.
updated on 01 November 2012.