Python如何使用函数实现二分查找算法

二分查找算法（Binary Search）是一种常用的查找算法，也称为折半查找，它的优点是时间复杂度为O(log n)。

二分查找算法的基本思路是：从有序序列的中间位置开始比较，如果查找元素比中间元素大，则在右半部分查找；如果查找元素比中间元素小，则在左半部分查找；如果查找元素等于中间元素，则查找成功。如果查找的范围缩小到只剩一个元素，仍然没找到时，则查找失败。

在Python中，使用函数实现二分查找算法可以提高代码的可读性和代码的复用性。下面我们来看一下如何使用函数实现二分查找算法。

步骤一：定义函数

我们首先需要定义一个二分查找算法的函数，在函数中需要传入两个参数， 个参数为要查找的有序序列，第二个参数为要查找的元素。

def binary_search(list, item):

    low = 0

    high = len(list)-1

    while low <= high:

        mid = (low + high) // 2

        guess = list[mid]

        if guess == item:

            return mid

        if guess > item:

            high = mid - 1

        else:

            low = mid + 1

    return None

在函数中，我们首先定义了两个变量low和high，用来表示查找的范围。初始时，low为0，high为序列的最大下标。然后使用一个while循环进行查找，每次循环中，我们先计算出中间元素的下标mid=(low+high)//2，然后找到中间元素的值guess=list[mid]。如果guess等于要查找的元素item，则返回中间元素的下标mid。如果guess大于item，则在左半部分查找，将high的值改为mid-1；如果guess小于item，则在右半部分查找，将low的值改为mid+1。循环直到查找范围缩小到只剩一个元素或未找到元素。

如果未找到要查找的元素item，则返回None。

步骤二：测试程序

在实现函数之后，我们需要编写一个测试程序来验证函数的功能。以下是一个简单的测试程序：

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3)) #输出2，即要查找的元素3在序列中的下标为2

print(binary_search(my_list, -1)) #输出None，即要查找的元素-1未找到

在测试程序中，我们定义了一个有序序列my_list。然后分别调用函数binary_search来查找元素3和元素-1在序列中的下标。程序输出2和None，验证了函数的正确性。

以上就是使用函数实现二分查找算法的过程，它可以帮助我们提高程序的可读性和可维护性，使我们能够更好地应对各种查找需求。