python 二分法查找

二分查找（搜索）是一种在有序列表中查找某一特定元素的搜索算法。

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

def binary_search(arr, l, r, x):
    if r > l:                   # 基本判断，右面的位置大于左面的位置
        mid = int(l + (r - l) / 2)          # 计算出中位数
        if arr[mid] == x:       # 元素正好中间的位置
            return mid
        elif arr[mid] > x:      # 查找的元素小于中间的元素的值
            return binary_search(arr, l, mid+1, x)
        else:                   # 查找的元素大于中间的元素的值
            return binary_search(arr, mid, r, x)
    else:
        return -1               # 不存在

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
 
#函数递归
#定义一个函数,给三个形参:低位值，高位值，查找值
def BinarySearch(low,height,findNum):
    #计算出中位数
    middle = (low+height)//2
    #如果中位数小于查找值,则锁定后半段
    if findNum >array[middle]:
        #重置低位数
        low = middle +1
    #如果中位数大于查找值,则锁定前半段
    elif findNum<array[middle]:
        #重置高位值
        height = middle - 1
    else:
        #找到该值并返回
        return '该值下标为:%s,值为:%s'%(middle,array[middle])
    #没有找到则调用自身继续查找
    return BinarySearch(low,height,findNum)
 
print(BinarySearch(array[0],len(array)-1,19))