python 二分查找的递归与非递归实现

二分查找定义

二分查找，又称折半查找，是对一组有序的数字进行查找，其思想如下：

1. 将待查的数据x与数字的中值mid进行比较，如相等则查找成功，返回x在arr中的索引；若x>mid，则执行2；若x<mid，则执行3
2. 只检查右边的数据，重复1，直到arr下标low>=high时结束
3. 只检查左边的数据，重复1，直到arr下标low>=high时结束

递归实现

import time

# 二分查找（递归实现）
def binarySearch(arr, low, high, x):
    '''
    该函数用于实现二分查找
    :param arr: 存储数据的数组
    :param low: 第一个元素的下标
    :param high: 最后一个元素下标
    :param x: 待查找的数据
    :return: mid，数据所在的索引
    '''

    if low <= high:
        mid = int((low + high) / 2)
        if x == arr[mid]:
            # 返回索引
            return mid

        # 元素小于中间位置元素，只需要再比较左边的元素
        if x < arr[mid]:
            return binarySearch(arr, low, mid - 1, x)

        # 元素大于中间位置元素，只需要再比较右边的元素
        if x > arr[mid]:
            return binarySearch(arr, mid + 1, high, x)

    else:
        return -1


# 测试数组
arr = ['a', 'b', 'c', 'd']
x = '1'

# 开始时间
start = time.clock()

# 函数调用
result = binarySearch(arr, 0, len(arr) - 1, x)

# 结束时间
end = time.clock()

# 输出
if result != -1:
    print('元素在数组中的索引为：{}'.format(result))

else:
    print('元素不在数组中！')

# 输出函数运行的时间
print(end - start)

非递归实现

# python非递归实现二分查找

def BinarySearch(arr, low, high, x):
    while True:
        if low <= high:
            mid = int((low + high) / 2)
            if arr[mid] == x:
                return mid
            elif x < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1

        else:
            return -1


# 测试数组
arr = [1, 2, 3, 4, 5, 6, 7, 8]
x = 10

# 调用函数
index = BinarySearch(arr, 0, len(arr) - 1, x)

# 输出结果
print('{x}在arr中的索引为{index}'.format(x=x, index=index))

注意本文在递归与非递归方法中，mid的取值公式mid = int(low + high) / 2，这里相当于是向下去取整了，即当arr = [1,2,3,4,5,6,7,8]时，low = 0，high = 7，此时，mid = int((0 + 7) / 2) = int(3.5) = 3，所以第一轮的比较是x与4进行比较，若此时x>4，则下一轮的比较则会变成x与6进行比较了，因为我们是向下取整，所以选的是6

补充

1. Python中math模块有专用的向下向上取整函数，以下以代码示例给出：

import math

f = 5.63
# 向上取整
print(math.ceil(f))
# 向下取整
print(math.floor(f))
# 四舍五入
print(round(f))
# 向下取整返回的类型
print(type(math.floor(f)))

执行结果

image.png
可以看到，取整函数返回的结果的类型是int，因此，上式mid = int(low + high) / 2也可以换成mid = math.floor((low + high) / 2)

2. 二分查找的关键在于mid = int(low + high) / 2，正式因为这个式子，我们才可以每次都从中间取一个数。根据实际情况，我们也可以修改该式子，比如：mid = int(low + high) / 3，mid取值方式不同，算法的性能也可能不同