Lectures‎ > ‎

Week13

Binary Search Index


def binary_search_index(x, nums, index):
    """Find the value x in the nums list using binary search.
       The complexity is O(lg n).
    """
    print nums

    if nums == []:
        return -1
    elif len(nums) == 1:
        if x == nums[0]:
            return index
        else:
            return -1
    else:
        midindex = len(nums) / 2
        midvalue = nums[midindex]
        if x == midvalue:
            return midindex + index
        elif x < midvalue:
            return binary_search_index(x, nums[0:midindex], index)
        elif x > midvalue:
            return binary_search_index(x, nums[midindex + 1:], index + midindex + 1)


numlist = [0,1,2,3,5,6,7,8,8,9,10,11,13,14,15,16,17]

print numlist
print binary_search_index(14, numlist, 0)
print binary_search_index(4, numlist, 0)
print binary_search_index(8, numlist, 0)

Comments