binsearch.py

"""
>>> a = [1, 2, 5, 12, 44, 83, 301, 404, 589, 700]
>>> binsearch([], 301)
False
>>> binsearch([301], 301)
True
>>> binsearch(a, 301)
True
>>> binsearch(a, 31337)
False
>>> binsearch_rec([], 301)
False
>>> binsearch_rec([301], 301)
True
>>> binsearch_rec(a, 589)
True
>>> binsearch_rec(a, 701)
False
>>> binsearch_rec(a, 700)
True
>>> binsearch_rec(a, 1)
True
"""


def binsearch(haystack, needle):
    start = 0
    end = len(haystack) - 1
    while start <= end:
        middle = (start + end) // 2
        if haystack[middle] == needle:
            return True
        if haystack[middle] > needle:
            end = middle - 1
        else:
            start = middle + 1
    return False


def binsearch_rec(haystack, needle):
    start = 0
    end = len(haystack) - 1
    if start > end:
        return False
    middle = (start + end) // 2
    if haystack[middle] == needle:
        return True
    if haystack[middle] > needle:
        return binsearch_rec(haystack[start:middle], needle)
    return binsearch_rec(haystack[middle+1:end+1], needle)

output.log

➜  bin-search  python -m  doctest -v binsearch.py
Trying:
    a = [1, 2, 5, 12, 44, 83, 301, 404, 589, 700]
Expecting nothing
ok
Trying:
    binsearch([], 301)
Expecting:
    False
ok
Trying:
    binsearch([301], 301)
Expecting:
    True
ok
Trying:
    binsearch(a, 301)
Expecting:
    True
ok
Trying:
    binsearch(a, 31337)
Expecting:
    False
ok
Trying:
    binsearch_rec([], 301)
Expecting:
    False
ok
Trying:
    binsearch_rec([301], 301)
Expecting:
    True
ok
Trying:
    binsearch_rec(a, 589)
Expecting:
    True
ok
Trying:
    binsearch_rec(a, 701)
Expecting:
    False
ok
Trying:
    binsearch_rec(a, 700)
Expecting:
    True
ok
Trying:
    binsearch_rec(a, 1)
Expecting:
    True
ok
2 items had no tests:
    binsearch.binsearch
    binsearch.binsearch_rec
1 items passed all tests:
  11 tests in binsearch
11 tests in 3 items.
11 passed and 0 failed.
Test passed.