Python递归实现二分查找算法
二分查找算法是一种常见的查找算法，也被称为折半查找算法。其基本思想是，将已排序的数据集合分成两个部分，取中间值进行比较，如果查询的值小于中间值，则在左侧继续查找；反之则在右侧继续查找。如此递归进行，直到找到或者查找范围为空。
下面是 Python 实现二分查找算法的代码：
def binary_search(arr, target): """ 递归实现二分查找算法 :param arr: 已排序的数组 :param target: 待查找的目标值 :return: 目标值在数组中的索引，如果不存在则返回 -1 """ if not arr: # 如果数组为空，说明查找范围已经缩小到最小，返回 -1 return -1 low, high = 0, len(arr) - 1 # 初始化查找范围的首位和末位索引 mid = (low + high) // 2 # 取中间值 if arr[mid] == target: # 如果中间值就是目标值，则直接返回 return mid elif arr[mid] < target: # 如果中间值小于目标值，说明目标值在右侧，继续查找右侧部分 return binary_search(arr[mid + 1:], target) + mid + 1 # 加上 mid + 1 是因为在右侧查找时已经舍弃了左侧部分，所以要加上 mid + 1 else: # 否则，中间值大于目标值，说明目标值在左侧，继续查找左侧部分 return binary_search(arr[:mid], target) # 测试 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 5 print(binary_search(arr, target)) # 输出：4 arr = ["pidancode.com", "皮蛋编程", "Python", "Java", "JavaScript"] target = "皮蛋编程" print(binary_search(arr, target)) # 输出：1
在上面的代码中，我们定义了一个 binary_search() 函数来递归地实现二分查找算法。该函数接收两个参数：已排序的数组和待查找的目标值。
首先，我们检查数组是否为空，如果是，则说明查找范围已经缩小到最小，返回 -1。
然后，我们初始化查找范围的首位和末位索引，计算中间值。
接着，我们比较中间值和目标值，如果相等，则直接返回中间索引；否则，如果中间值小于目标值，则说明目标值在右侧，继续查找右侧部分；如果中间值大于目标值，则说明目标值在左侧，继续查找左侧部分。
注：对于字符串的二分查找，其基本思路和整型数据相同，只是比较时用字符串本身的比较方式即可。
相关文章