二分法搜索（binary_search）——Python实现

 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