When a list is sorted, a high-speed binary search technique can find items in the list quickly. The binary search algorithm eliminates from consideration one-half of the elements in the list being searched after each comparison. The algorithm locates the middle element of the list and compares it with the search key. If they are equal, the search key is found, and the subscript of that element is

returned. Otherwise, the problem is reduced to searching one half of the list. If the search key is less than the middle element of the list, the first half of the list is searched. If the search key is not the middle element in the specified piece of the original list, the algorithm is repeated on one-quarter of the original list. The search continues until the search key is equal to the middle ele- ment of the smaller list or until the smaller list consists of one element that is not equal to the search key (i.e. the search key is not found.) Even in a worst-case scenario, searching a list of 1024 elements will take only 10 comparisons during a binary search. Repeatedly dividing 1024 by 2 (because after each comparison we are able to eliminate from the consideration half the list) yields the values 512, 256, 128, 64, 32, 16, 8, 4, 2 and 1. The number 1024 (210) is divided by 2 only ten times to get the value 1. Dividing by 2 is equiva- lent to one comparison in the binary-search algorithm. A list of 1,048,576 (2 20) elements takes a maximum of 20 comparisons to find the key. A list of one billion elements takes a maximum of 30 comparisons to find the key. The maximum number of comparisons needed for the binary search of any sorted list can be determined by finding the first power of 2 greater than or equal to the number of elements in the list. Write a program that implements function binarySearch, which takes a sorted list and a search key as arguments. The function should return the index of the list value that matches the search key (or -1, if the search key is not found).

What will be an ideal response?

```
# Binary search of a list sorted in ascending order.

import random

def binarySearch( bList, key ):
low = 0 # low subscript
high = len( bList ) - 1 # high subscript

while low <= high:
middle = ( low + high ) / 2 # middle subscript

if key == bList[ middle ]: # match
return middle;
elif key < bList[ middle ]: # search low end of list
high = middle - 1
else:
low = middle + 1 # search high end of list

return -1 # search key not found

# main program

binarySearchList = range( 1, 10 ) # create list of integers 1-10

# randomly select a search key
searchKey = random.randrange( 1, 20 )

# call binarySearch function
index = binarySearch( binarySearchList, searchKey )

# search key found
if index > 0:
print "Search key %d was found at index %d." % \
( searchKey, index )
else:
print "Search key %d was not found in list." % ( searchKey )
```
Search key 3 was found at index 2.
Search key 18 was not found in list.