Binary Search

Binary Search is one of the most fundamental computer algorithms. Given an ordered list of some data (names, numbers, …) find out if it contains a particular item. For example, consider the list: 2, 4, 5, 7, 8, 11, 12. If we ask if it contains the number 5, the algorithm should return 2 (counting from 0). If we ask if it contains 9 the algorithm can return a value that can’t be a position, such as -1, to indicate the number wasn’t found. In practice, the list would comprise records containing the key, e.g. a name, and some associated data, e.g. a telephone number.

If you don’t know anything about how the keys are distributed, e.g. evenly, one good strategy would be to start your search in the middle. If you don’t find it immediately, compare it with the item in the middle – is it smaller or larger than that? If it’s larger, try looking in the middle of the top half of the list, other wise look in the middle of the bottom half of the list. This is a recursive procedure.

# BinarySearch.py
#	Alan Richmond, Python3.codes

import random

anum = 9                    # number to search for
size = 10                   # size of random array
array = random.sample(list(range(1, 20)), size)  # get some random numbers
array = sorted(array)       # sorted() returns a new list
#array.sort()				# sort() sorts in-place
print(anum, array)          # show us what you've got

#    Search for number in array
def binary_search(number, array, lo, hi):

    if hi < lo: return -1       # no more numbers
    mid = (lo + hi) // 2        # midpoint in array
    if number == array[mid]:
        return mid                  # number found here
    elif number < array[mid]:
        return binary_search(number, array, lo, mid - 1)     # try left of here
    else:
        return binary_search(number, array, mid + 1, hi)     # try above here

def my_search(anum, array):     # convenience interface to binary_search()
    return binary_search(anum, array, 0, len(array) - 1)

pos = my_search(anum, array)
if pos < 0:
    print("not found")
else:
    print("found at position", pos)

Click here to try it out!