Python二分查找实现

Posted in 2016-8-5 20:55 | Category: Python | Tags: python 算法 二分查找

三种方法实现:

def find(a, low, high, v):
    mid = low + (high - low) // 2
    if v < a[0] or v > a[-1]:
        return False
    if mid >= len(a):
        return False
    if a[mid] == v:
        return True
    elif a[mid] > v:
        return find(a, low, mid - 1, v)
    else:
        return find(a, mid + 1, high, v)

def find2(a, low, high, v):
    mid = low + (high - low) // 2
    if v < a[0] or v > a[-1]:
        return False
    if a[mid] == v:
        return True
    elif a[mid] < v:
        low = mid
    else:
        high = mid
    return find2(a, low, high, v)

def find3(a, v):
    n = len(a)
    low = -1
    high = n
    ret = True
    while (low + 1 != high):
        mid = low + (high - low) // 2
        if (a[mid] == v …