人人都爱Binary Search

Recursion

 def bs(target, nums):
   if not nums:
        return False

    mid = len(nums)//2
    if nums[mid] == target:
        return True
    elif  target < nums[mid]:
        return bs(target, nums[:mid])
    else:
        return bs(target, nums[mid+1:])


nums = [1, 2, 3, 5, 6, 9]
for n in nums:
    print bs(n, nums)
print bs(0, nums)
print bs(10, nums)

Iteration

def bs(target, nums):
    if not nums:
        return False

    l, r = 0, len(nums)
    while l < r:
        mid = (l+r)//2
        if nums[mid] == target:
            return True
        elif target < nums[mid]:
            r = mid
        else:
            l = mid + 1
    return False


nums = [1, 2, 3, 5, 6, 9]
for n in nums:
    print bs(n, nums)
print bs(0, nums)
print bs(8, nums)
print bs(10, nums)