解决问题:
给定一个有序的列表, 一个待查找的目标值, 判断目标值是否在有序的列表中, 并返回目标值在列表中的索引
实现步骤:
1. 因为是一个有序的列表, 起始最小值为第一个元素, 起始最大值为最后一个元素
2. 取列表的中间索引处值与目标值进行比较, 根据判断结果, 剔除列表左侧一半元素或右侧一半元素
(1)如果目标值大于列表中间值, 那么目标值一定位于列表右侧一半元素中; 最小值为列表中间索引+1处的值(为什么加一, 因为中间索引处的值已经比目标值小了, 所以中间索引处的值可以剔除)
(2)如果目标值小于列表中间值, 那么目标值一定位于列表左侧一半元素中; 最大值为列表中间索引-1处的值(为什么减一, 因为中间索引处的值已经比目标值大了, 所以中间索引处的值可以剔除)
3. 取剩余元素的中间值与目标值进行比较, 根据比较结果, 继续剔除一半元素, 直到找到目标值
4. 直到最大值与最小值相等(列表中仅剩一个元素时), 还没有找到与目标值匹配的值, 说明目标值不在列表中
###实现过程中, 根据中间索引处的值与目标值的比较结果, 最大最小值一直在动态变化(这里的最大最小值是为了确定查找范围的边界)
代码:
def binarySearch(seq, target):
'''
返回目标值在有序序列中的索引
:param seq: 有序序列
:param target: 待查找目标值
:return: 找到: 返回索引; 未找到: 返回-1
'''
min_index = 0 #最小值的索引
max_index = len(seq) - 1 #最大值的索引
while min_index <= max_index: #只要序列中还有元素存在
mid_index = (min_index + max_index) // 2 #地板除, 向上取整
if target > seq[mid_index]:
min_index = mid_index + 1
elif target < seq[mid_index]:
max_index = mid_index - 1
else:
return mid_index
return -1
# 测试
lst = [1, 3, 5, 8, 10, 15, 20]
r = binarySearch(lst, 15)
print(r)