binarysearchtests.py

"""
Test out 20 binary-search functions harvested from
http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
See results at the bottom.
"""

import random

failures = {}

def test(search):
    """Test that the given search function obeys the contract:

    If array is sorted ascending, then search(array, key) returns a j
    such that array[j] == key, if possible; else -1.

    Report whether it passes, giving a failing test case if it fails.
    (We don't try to interrupt infinite loops -- we didn't happen to
    get any.)"""

    ok1 = test_passes(test_randomly, search)
    ok0 = test_passes(test_search, search)
    #assert ok0 == ok1  # (To see if either tester beats the other)
    if ok0 and ok1:
        print 'PASS: %s' % search.__name__
    else:
        if ok0 or ok1:
            # only one of the testers passed!
            print "------ Only one tester passed for %s! ---- " % search.__name__
            print "Random failures: %s" % str(failures.get((search, 'random')))
            print "Exhaustive failures: %s" % str(failures.get((search, 'exhaustive')))
            print "-------------------------------------------"
        else:
            print '    : %s\t%s' % (test_case, search.__name__)

def test_passes(test_it, function):
    try:
        test_it(function)
    except:
        return False
    return True

test_case = "Can't happen"

def test_randomly(search):
    global test_case
    for length in xrange(10):
        for times in xrange(100):
            array = random_array(length, length)
            array.sort()
            key = random.randint(-1, length)
            test_case = (array, key)
            try:
                j = search(array, key)
                if j == -1:
                    assert key not in array
                else:
                    assert 0 <= j < length
                    assert key == array[j]
            except:
                failures[(search, 'random')] = test_case
                raise

def random_array(length, hibound):
    return [random.randint(0, hibound-1) for i in xrange(length)]

def test_search(search):
    """An 'exhaustive' tester following the 0-1 principle: if a
    function fails on any input, we can expect it to fail on some
    input using just 0's and 1's. I don't know if this is a theorem as
    it is for sorting networks, but it happened to work here! Heh."""
    for length in xrange(20):
        for boundary in range(length + 1):
            array = [0]*boundary + [1]*(length-boundary)

            def expect(key, lo, hi=-1):
                "Check that search finds key in [lo..hi) (or -1 if absent)."
                global test_case
                test_case = (array, key)
                if lo < hi:
                    assert lo <= search(array, key) < hi
                else:
                    assert -1 == search(array, key)

            try:
                expect(0, 0, boundary)
                expect(1, boundary, length)
            except:
                failures[(search, 'exhaustive')] = test_case
                raise
            # And the following tests seem redundant in practice -- no
            # extra failures found with them:
            # expect(-1, -1) 
            # expect(2, -1)


# Now for the harvested functions

def patrick_shields(array, key):
    def bsearch(listy, val, index):
        if len(listy) == 1:
            if listy[0] != val:
                #print "ERRRRRRRRRRRRROOOOOOOOOOOOOOORRRRRRRRRRRRRRRRRRRRRR"
                return -1
            else:
                return index
        else:
            new_ind = len(listy)/2
            if listy[new_ind] == val:
                return index+new_ind
            elif listy[new_ind] < val:
                return(bsearch(listy[new_ind+1:], val, index+new_ind+1))
            else:
                return(bsearch(listy[:new_ind], val, index))
    return bsearch(array, key, 0)

# Fail: Throws an error:
test(patrick_shields)

def ed_marshall(range, target):
    crange = range
    offset = 0
    while True:
        ctarget = len(crange) / 2
        if crange[ctarget] == target:
            return ctarget + offset
        elif crange[ctarget] > target:
            crange = crange[:ctarget]
        else:
            crange = crange[ctarget+1:]
            offset += ctarget+1
        if len(crange) == 0:
            return -1

# Fail: Also throws an error:
test(ed_marshall)

def ashish_yadav(array, key):
    def bsearch(arr,key,start=0,end=None):
        if end == None: end = len(arr) - 1
        if start > end: return None
        if start == end and arr[start] != key: return None

        mid = (start+end)/2
        if arr[mid] == key:
            return mid
        if arr[mid] > key:
            return bsearch(arr,key,start,mid-1)
        if arr[mid] < key:
            return bsearch(arr,key,mid+1,end)
    i = bsearch(array, key)
    return -1 if i is None else i


# passes
test(ashish_yadav)

def travis(lst, item):
    bottom, top = 0, len(lst)

    while top - bottom >= 3:
        mid = (top + bottom) // 2

        c = cmp(item, lst[mid])

        if c < 0:
            bottom = mid + 1
        else:
            return True

        if item == lst[bottom]:
            return True

    return top - bottom == 2 and item == lst[bottom + 1]

# Fails: #.     assert search(array, -1) == -1
# N.B. this one only returns success or failure, not an index;
# so it's incompatible with this test suite.
test(travis)


def dan(l, n):
    H = len(l) - 1
    L = 0
    M = int(H / 2)

    while H - L > 0 and n != l[M]:
        if n > l[M]:
            L = M
        else:
            H = M
            M = int((H + L) / 2)

    if n == l[M]:
        return M

    return -1

# Fails: #. IndexError: list index out of range
test(dan)


def ben_gutierrez(l, needle):
    start, end = 0, len(l)-1

    while start <= end:
        mid = (start + end) / 2
        if l[mid] == needle:
            return mid
        elif l[mid] < needle:
            start = mid + 1
        else:
            end = mid - 1
    return -1

# Passes, but N.B. it'd need // instead of / in Python 3
test(ben_gutierrez)


def si(array, key):
    def bsearch(nums, item):
        while nums:
            mid = len(nums) / 2

            if nums[mid] > item:
                nums = nums[:mid]

            elif nums[mid] < item:
                nums = nums[mid+1:]

            else:
                return True

        return False

    if bsearch(array, key):
        return array.index(key)
    return -1

# Passes
test(si)


def aaron_maxwell(array, key):
    def bsearch(needle, haystack):
        lower = 0
        upper = len(haystack) - 1
        idx = int(upper/2)
        found = haystack[idx] == needle
        while not found:
            if lower >= upper:
                break
            if needle > haystack[idx]:
                lower = idx + 1
            else:
                upper = idx - 1
            idx = int(.5 *(lower + upper))
            found = haystack[idx] == needle
        if found:
            return idx # found it!
        return False # indicating item not in the list

    j = bsearch(key, array)
    return -1 if j is False else j

# Fails: #. IndexError: list index out of range
test(aaron_maxwell)


def Max(array, key):
    def bsearch(srtd,x):
        l = len(srtd)
        if l == 0:
            return False
        med = srtd[l/2]
        #print med
        if med == x:
            return True
        if x < med:
            return bsearch(srtd[:(l/2)],x)
        else:
            return bsearch(srtd[(l/2)+1:],x)
    return array.index(key) if bsearch(array, key) else -1

# Pass
test(Max)


def clark(data, toFind):
    begin = 0
    end = len(data) - 1

    while begin < (end - 1):
        pivot = int(begin + (end - begin) / 2)

        if data[pivot] == toFind:
            return pivot
        elif data[pivot] < toFind:
            end = pivot

        if data[begin] == toFind:
            return begin
        elif data[end] == toFind:
            return end

    return -1

# Fails: #.     assert boundary <= search(array, 1) < length
test(clark)


def martin(array, key):
    def bsearch(needle, slice):
	if len(slice) == 1:
            if slice[0] == needle:
                return needle
            else:
                return None
	p = len(slice) // 2
	if slice[p] > needle: return bsearch(needle, slice[:p])
	else:                 return bsearch(needle, slice[p:])

    i = bsearch(key, array)
    return -1 if i is None else i


# Fails: #. IndexError: list index out of range
test(martin)


def paul(array, key):
    def binsearch_iterative(t, seq):
        """
        Return index where target `t` is found in ordered sequence `seq`.
        If t is not found, return None.
        """
        left = 0
        right = len(seq) - 1
        while right >= left:
            mid = (right + left) // 2
            if seq[mid] == t:
                return mid
            elif seq[mid] > t:
                right = mid -1
                continue
            else:
                left = mid +1
                continue
        return None

    i = binsearch_iterative(key, array)
    return -1 if i is None else i

# passes
test(paul)



def dave_r(array, key):
    def bsearch(haystack, needle):
        start = 0
        length = len(haystack)
        end = length - 1
        idx = length / 2
        while True:
            val = haystack[idx]
            if val == needle:
                return idx
            elif val > needle:
                end = idx
            elif val < needle:
                start = idx
            idx = start + ((end - start) / 2)

    i = bsearch(array, key)
    return -1 if i is None else i

# Fails: #. IndexError: list index out of range
test(dave_r)


def scott(array, key):
    from math import ceil

    def bsearch(needle, haystack):
        top = len(haystack)-1
        bottom = 0

        # check that needle can still possibly exist in haystack
        if (not haystack) or haystack[-1] < needle or haystack[0] > needle:
            return None

        # get a value for middle val
        middle = (len(haystack) - (len(haystack)%2)) / 2
        middle_val = haystack[middle]

        # check value
        if needle == middle_val:
            return middle
        elif needle < middle_val:
            return bsearch(needle, haystack[:middle])
        else:
            return middle + 1 + bsearch(needle, haystack[middle+1:])

    i = bsearch(key, array)
    return -1 if i is None else i

# Fails:
# XXX Blew up the `assert ok0 == ok1` check!
# This raises TypeError on recursive calls since it potentially
# adds middle + 1 + None in the final `else` clause. Only caught by the random tests, not the 
# 'exhaustive' tests.  Typical failing input has some repeated values:  ([0, 0, 2], 1)
test(scott)


def michael_fogleman(array, value):
    a = 0
    b = len(array) - 1
    while a <= b:
        m = (b - a) / 2 + a
        if array[m] == value:
            return m
        elif array[m] > value:
            b = m - 1
        else:
            a = m + 1
    return -1

# Pass
test(michael_fogleman)


def rodrigo_b(ary, val):
    lo = 0
    hi = len(ary)
    oldm = -1
    while True:
        m = int((lo+hi)/2)
        if oldm == m:
            return -1
        if val < ary[m]:
            oldm = m
            lo = m
        else:
            return m

# Fails: #. IndexError: list index out of range
test(rodrigo_b)


def jasper(array, key):
    def bsearch(li, val, lo=None, up=None):
        if lo is None or up is None:
            lo = 0
            up = len(li)

            # check that the value is inside the list
            if val < li[lo]:
                return None
            if val > li[up - 1]:
                return None
        print li, val, lo, up

        # the interval to check is [lo, up), check its size
        if (up - lo) <= 1:
            if li[lo] == val:
                return lo
            else:
                return None

        # slice and dice!
        mid = (lo + up) / 2

        if (li[mid] <= val):
            return bsearch(li, val, mid, up)
        else:
            return bsearch(li, val, lo, mid)

    i = bsearch(array, key)
    return -1 if i is None else i

# Fails: #. IndexError: list index out of range

test(jasper)


def tomas_henriquez(array, key):
    def bs(array,findme):
        if(array):
            array = sorted(array)
            len = array.__len__()

            pos=len/2
            mid=len/2+1

            while(mid):
                #trunk because its an integer
                if mid%2 and mid != 1: mid=mid/2+1
                else: mid=mid/2
                if (findme == array[pos]):
                    return array[pos]
                elif (findme > array[pos]):
                    pos+=mid
                elif (findme < len-1 or pos < 0): break

        return "None"
    j = bs(array, key)
    return -1 if j is "None" else j

# Fails: #.     assert boundary <= search(array, 1) < length
test(tomas_henriquez)


# Returns the index of data in inArray, or -1 if none found
def yc(inArray, data):
    start = 0
    end = len(inArray) - 1
    if end < start:
        return -1
    if data < inArray[0] or data > inArray[-1]:
        return -1
    while (True):
        if (start == end):
            if data == inArray[start]:
                return start
            else:
                return -1
        middle = start + ((end-start) / 2)
        if (data == inArray[middle]):
            return middle
        elif (data < inArray[middle]):
            end = middle
        else:
            start = middle + 1

# Pass
test(yc)


def guilherme_melo(array, key):
    def binary_search(a_list, elem):
	if not a_list:
            return False
	index = len(a_list)/2

	ret = cmp(elem, a_list[index])

	if ret < 0:
            return binary_search(a_list[0:index], elem)
	elif ret > 0:
            return binary_search(a_list[index + 1:len(a_list)], elem)
	else:
            return True
    return array.index(key) if binary_search(array, key) else -1

# Pass
test(guilherme_melo)


# Finally, the output. The ones that don't say PASS failed; the middle
# column holds the first failing test case.
# Of the 8 that pass, 4 of them must be O(n) since they use array slicing.
# So overall, we get 4 of 20 that succeed with O(log(n)) -- though I don't
# actually measure the time complexity.
# 
# I also would have included Luke Stebbing's function, which appears correct,
# except it obeys a different contract; that'd make 5 of 21 submissions good.
# There were a couple more I skipped for looking like too much trouble to
# get into a testable format; I wouldn't bet on them raising the average.
# (I had to reindent and de-HTMLize many of the others; this could conceivably
# have introduced errors.) Otherwise I just picked up every Python entry until
# I got tired, going at first from the start, and then from the end.
# 
# My main motivation was to try out 'exhaustive' testing with the 0-1
# principle. It found nearly all of the same bugs as a random test, *except* one
# failure in the scott() function that was only found by random tests.
# Neither tester uncovered any infinite loops -- I wonder if there are
# any they missed? Incidentally many of the failing functions here were
# certified by their authors -- passed their own tests.

#.     : ([], 0)	patrick_shields
#.     : ([], 0)	ed_marshall
#. PASS: ashish_yadav
#.     : ([], 0)	travis
#.     : ([], 0)	dan
#. PASS: ben_gutierrez
#. PASS: si
#.     : ([], 0)	aaron_maxwell
#. PASS: Max
#.     : ([1], 1)	clark
#.     : ([], 0)	martin
#. PASS: paul
#.     : ([], 0)	dave_r
#. ------ Only one tester passed for scott! ---- 
#. Random failures: ([0, 0, 2], 1)
#. Exhaustive failures: None
#. -------------------------------------------
#. PASS: michael_fogleman
#.     : ([], 0)	rodrigo_b
#.     : ([], 0)	jasper
#.     : ([1], 1)	tomas_henriquez
#. PASS: yc
#. PASS: guilherme_melo