二分查找算法--Python语言描述

当列表的数据是有序的情况下， 使用二分查找算法是非常高效的, 以下使用两种方式实现了二分查找。

二分查找的一般算法描述：

# 二分查找算法
print('二分查找算法')
def binary_search(data, item):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = int((low + high) / 2)
        if data[mid] == item:
            return mid
        elif data[mid] > item:
            high = mid -1
        else:
            low = mid + 1
    return None

my_list2 = [1, 3, 5, 7, 9]
print(binary_search(my_list2, 7))

输出结果：

>>> 二分查找算法
>>> 3

------------------------------------分割线------------------------------------------------

二分查找算法的递归实现：

# 二分查找算法(递归描述)
print('二分查找算法(递归描述)')
def binary_search(low, high, data, item):
    if data[low] <= item <= data[high]:
        mid = int((low + high) / 2)
        if item == data[mid]:
            return mid
        elif item > data[mid]:
            return binary_search(mid + 1, high, data, item) 
        else:
            return binary_search(low, mid - 1, data, item)
    else:
        return None

my_list1 = [1, 3, 5, 7, 9, 11, 13, 15, 17]
print(binary_search(0, len(my_list1)-1, my_list1, 17))

输出结果：

>>> 二分查找算法(递归描述)
>>> 8