二分查找递归、非递归实现（Python）

二分查找

二分查找中，会不断将一个有序数组折半，大幅缩小查询的范围，直到找到目标元素的位置。

优缺点

优点：元素比较次数少，查找速度快，稳定性好
缺点：要查询的数组必须是有序数组

代码实现（非递归）

# 二分查找
def binary_search(array,x):
    '''
    array: 目标数组（必须有序）
    x: 要查询的元素
    
    '''
    left = 0                   # 指定左指针变量
    right = len(array) - 1     # 指定右指针变量
    while left < right:
        mid = left + ((right - left) >> 1)    # 数组中间元素的index（这种形式防止有数据溢出）
        if array[mid] > x:       # 如果 x 小于中间元素，说明 x 在数组的左半部分，故更新右指针变量
            right = mid
        elif array[mid] < x:     # 如果 x 大于中间元素，说明 x 在数组的右半部分，故更新左指针变量
            left = mid
        else:
            return mid
    return -1

验证：

输入：
array = [1,4,7,9,10,34,576,989]
binary_search(array,34)
输出：5

代码实现（递归）

def binary_search(array,left,right,x):
    '''
    array: 目标数组（必须有序）
    left: 数组的左指针变量
    right: 数组的右指针变量
    x: 要查询的元素
    
    '''
    mid = left + ((right - left) >> 1)   # 数组中间元素的index（这种形式防止有数据溢出）
    if left > right:
        return -1
    if array[mid] > x:       # 如果 x 小于中间元素，说明 x 在数组的左半部分，故更新右指针变量，用递归实现
        return bi(array,left,mid,x)
    elif array[mid] < x:    # 如果 x 大于中间元素，说明 x 在数组的右半部分，故更新左指针变量，用递归实现
        return bi(array,mid,right,x)
    else:
        return mid

验证：

输入：
array = [1,4,7,9,10,34,576,989]
binary_search(array,0,len(array)-1,34)
输出：5