二分法搜索(binary_search)——Python实现

2019年11月6日15:41:28 发表评论 167 views

# 二分搜索

# 输入:按从小到大顺序排列的数组A,要搜索的数num

# 输出:如果搜索到,则输出该元素的位置,如果没有搜索到,则输出“没有搜索到该值”;并且输出比较次数count_compare

 1import math
 2 3def binary_search(A,num):
 4 5print('\n 输入的数组为:',A)
 6print(' 要搜索的数为:',num)
 7 8     n = len(A)               # n            数组长度 9     low = 0                  # low          指向低地址的指针10     high = n-1               # high         指向高地址的指针11     num_location = -1        # num_location 要搜索的元素的位置12     count_compare = 0        
131415while high - low > 1 and num_location == -1:
1617         mid = ( (low + high)/2 )          # mid 指向low和high中心元素的指针,floor表示向下取整1819if A[mid] == num:
20             num_location = mid                      # 当且仅当找到要搜索的值,才会改变num_location的值 21elif A[mid] <= num:
22             low = mid
23else:
24             high = mid
2526         count_compare = count_compare + 1
2728# print('第i趟搜索:',count_compare)
29# print('mid ',mid);print('low ',low);print('high ',high)
303132if high - low == 1:                             # 如果指针指向相邻的两个元素,那么要搜索的值要么是这两个元素其一,要么不存在33if A[low] == num:
34             num_location = low
35elif A[high] == num:
36             num_location = high
37         count_compare = count_compare + 1
38# 注:极少数情况下,若最后两个数相等,且都为要搜索的数,则通过此if判断语句后,num_location会变为high,也就是只会输出后面的元素的位置394041if num_location == -1:                          # 说明没有搜索到要搜索的值42print('\n 没有搜索到该值')
43print(' 比较次数为:', count_compare)
44else:
45print('\n 在该数组的位置:', num_location+1)
46print(' 比较次数为:', count_compare)

函数调用

1 A = [-39, -22, -1, 5, 12, 21, 33, 56, 56, 76, 92, 92, 110, 999]
2 num = 110
3 binary_search(A,num)

运行结果

 输入的数组为: [-39, -22, -1, 5, 12, 21, 33, 56, 56, 76, 92, 92, 110, 999]
 要搜索的数为: 110

 在该数组的位置: 13
 比较次数为: 4

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: