二分查找（递归和迭代）– Python

1. 利用递归进行二分查找的 Python 程序

   创建一个递归函数，并将搜索空间的 mid 与 key 进行比力。根据效果，要么返回找到键的索引，要么调用下一个搜索空间的递归函数。

1. # 用于递归二进制搜索的 Python 3 程序。
2. # 在注释中可以找到对旧版 Python 2 所需的修改。
4. # 如果存在，则返回 arr 中 x 的索引，否则返回 -1
5. def binary_search(arr, low, high, x):
7.     # Check base case
8.     if high >= low:
10.         mid = (high + low) // 2
12.        # 如果元素本身存在于中间
13.         if arr[mid] == x:
14.             return mid
16.                 # 如果元素小于中间值，则它只能出现在左子数组中
17.         elif arr[mid] > x:
18.             return binary_search(arr, low, mid - 1, x)
20.                 # 否则该元素只能出现在右子数组中
21.         else:
22.             return binary_search(arr, mid + 1, high, x)
24.     else:
25.         # 元素不在数组中
26.         return -1
28. # Test array
29. arr = [ 2, 3, 4, 10, 40 ]
30. x = 10
32. # Function call
33. result = binary_search(arr, 0, len(arr)-1, x)
35. if result != -1:
36.     print("元素存在于索引", str(result))
37. else:
38.     print("数组中不存在元素")

复制代码

输出

1. 元素位于索引 3

复制代码

时间复杂度：O（log n）
辅助空格：O（logn） [注意：递归创建调用堆栈]
2. 利用迭代进行二分查找的 Python 程序

   这里我们利用 while 循环来继续比力键并将搜索空间分成两半的过程。

1. # 迭代二分搜索函数
2. # 如果存在，则返回给定数组 arr 中 x 的索引，
3. # 否则返回 -1
4. def binary_search(arr, x):
5.     low = 0
6.     high = len(arr) - 1
7.     mid = 0
9.     while low <= high:
11.         mid = (high + low) // 2
13.         # 如果 x 更大，则忽略左半部分
14.         if arr[mid] < x:
15.             low = mid + 1
17.         # 如果 x 较小，则忽略右半部分
18.         elif arr[mid] > x:
19.             high = mid - 1
21.         # 表示 x 出现在中间
22.         else:
23.             return mid
25.     # 如果我们到达这里，则该元素不存在
26.     return -1
28. # 测试数组
29. arr = [ 2, 3, 4, 10, 40 ]
30. x = 10
32. # 函数调用
33. result = binary_search(arr, x)
35. if result != -1:
36.     print("元素存在于索引", str(result))
37. else:
38.     print("数组中不存在元素")

复制代码

输出

1. 元素位于索引 3

复制代码

时间复杂度：O（log n）
辅助空间：O（1）
3. 利用内置的 bisect 模块进行二分查找的 Python 程序

分步方法：

• 代码导入 bisect 模块，该模块提供对二分查找的支持。
  
• 界说binary_search_bisect() 函数的界说是将数组 arr 和要搜索的元素 x 作为输入。
  
• 该函数调用 bisect 模块的 bisect_left() 函数，该函数查找元素在排序数组 arr 中的位置，其中应插入 x 以保持排序顺序。如果元素已存在于数组中，则此函数将返回其位置。
  
• 然后，该函数检查返回的索引 i 是否在数组范围内，以及该索引处的元素是否等于 x。
  
• 如果条件为 true，则函数返回索引 i 作为元素在数组中的位置。
  
• 如果条件为 false，则函数返回 -1，指示数组中不存在该元素。
  
• 然后，该代码界说一个数组 arr 和一个要搜索的元素 x。
  
• 调用 binary_search_bisect（） 函数时，将 arr 和 x 作为输入，返回的效果存储在 result 变量中。
  
• 然后，代码检查效果是否不等于 -1，这表示该元素存在于数组中。如果为 true，则打印元素在数组中的位置。
  
• 如果效果等于 -1，则代码将打印一条消息，指出该元素不存在于数组中。
  

1. import bisect
3. def binary_search_bisect(arr, x):
4.     i = bisect.bisect_left(arr, x)
5.     if i != len(arr) and arr[i] == x:
6.         return i
7.     else:
8.         return -1
11. # Test array
12. arr = [2, 3, 4, 10, 40]
13. x = 10
15. # 测试数组
16. result = binary_search_bisect(arr, x)
18. if result != -1:
19.     print("元素存在于索引", str(result))
20. else:
21.     print("数组中不存在元素")

复制代码

输出

1. 元素位于索引 3

复制代码

时间复杂度：O（log n）
辅助空间：O（1）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。