Binary search

README.md

Binary search implementation in python.

Usage

from binary_search import search

arr = [2, 3, 4]

key = 3
i = search(arr, key)    # returns index of key value if found
assert arr[i] == key

key = 5
i = search(arr, key)    # returns `None` if key value is not found
assert i == None

binary_search.py

'''
Do a binary search for key value `k` in the array of sorted values 
`arr`.  Return the index `i` of the first matching value.

The recursive calls search for `k` within subarrays of `arr` where 
`l` specifies the lower (or "left") index and `r` specifies the upper 
(or "right") index of the subarray to be searched.

'''
def search(arr, k, l=0, r=None):
    if r is None: r = len(arr) - 1
    if r < l: return None
    i = ((r - l) // 2) + l              # index of middle element
    m = arr[i]                          # value of middle element
    if m > k:
        r = i - 1                       # search lower sub-array
        return search(arr, k, l, r)
    elif m < k:
        l = i + 1                       # search upper sub-array
        return search(arr, k, l, r)
    else:
        return i                        # found!

test.py

from binary_search import search

for x in range(4):
    arr = [0, 1, 2, 3]
    i = search(arr, x)
    assert i == x

arr = [1]
i = search(arr, 1)
assert i == 0

arr = [1]
i = search(arr, 2)
assert i == None

arr = [2, 3, 4]
key = 3
i = search(arr, key)
assert key == arr[i]