gistfile1.txt

def binary_search(target, nums):
    # see if target appears in nums

    # the number /cannot/ be at floor_index or ceiling_index--
    # floor and ceiling are "just outside" the range of possibilities
    floor_index = -1
    ceiling_index = len(nums)

    # if there isn't at least 1 index between floor and ceiling,
    # we've run out of guesses and the number must not be present
    while floor_index + 1 < ceiling_index:

        # find the index ~halfway between the two
        # we use integer division,
        # so we'll never get a "half index"
        distance = ceiling_index - floor_index
        half_distance = distance / 2
        guess_index = floor_index + half_distance

        guess_value = nums[guess_index]

        print {
            'guess_index': guess_index,
            'guess_value': guess_value,
            'floor_index': floor_index,
            'ceiling_index': ceiling_index,
            }

        if guess_value == target:
            return True

        if guess_value > target:
            # target is to the left
            # so move ceiling to the left
            ceiling_index = guess_index
        else:
            # target is to the right
            # so move floor to the right
            floor_index = guess_index

    return False


test_cases = [
    {
        'in': (5, [1,2,3,4,5,6,7,7]),
        'out': True,
        },
    {
        'in': (5, [1,2,3,4,5]),
        'out': True,
        },
    {
        'in': (5, []),
        'out': False,
        },
    {
        'in': (5, [1,2,3,4]),
        'out': False,
        },
    {
        'in': (5, [1,2,3,4,6,7,7]),
        'out': False,
        },
]

def test():
    for test_case in test_cases:
        print test_case
        out = binary_search(*test_case['in'])
        assert  out == test_case['out']
        print "passed"

test()