本文是根据数据结构中常常提到的二分法而作的一篇博客,主要通过一个二分法实例进行展开说明:
实例内容
通过一个二分法函数来寻找某个数是否在给定的数组中;
代码展示
# 执行二分查找法的算法函数
# 二分法查找的对象必须是一个有序的集合,
# 如果找到相应的元素则返回其索引位置,否则返回None
def binsearch(list, search_value):# 指定查找数据集的起始索引low_index = 0# 指定查找数据集的结束索引high_index = len(list) - 1# 当起始索引小于结束索引时,表示数据集中数据还可二分,# 提示:我们将每次二分后得到两个半区称为分区while (low_index <= high_index):# 取出当前查找数据集中间位置的索引值,round()取得整数mid_index = round((low_index + high_index) / 2)# 取出当前分区的中间位置的数值mid_value = list[mid_index]# 如果中间位置数值的数值等于要查找的数值if (mid_value == search_value):# 返回找到数值的索引值return mid_index# 如果中间位置数值的数值大于要查找的数值if (mid_value > search_value):# 将查找范围的结束索引值设为原分区中间位置的索引值-1high_index = mid_index - 1else:# 如果中间位置数值的数值小于要查找的数值# 将查找范围的起始索引值设为原分区中间位置的索引值+1low_index = mid_index + 1return None# 提供一个测试用的有序列表
test_list = [1, 2, 3, 5, 8, 33, 55, 67, 88, 99, 203, 211, 985]
# 录入要查找的数值
search_value = int(input('请录要查找的数值:'))
vret = binsearch(test_list, search_value)
if vret:print('你在', test_list, '中查找:', search_value)print('查找结果:', search_value, '在数据集中索引值是:', vret)
else:print('你在', test_list, '中查找:', search_value)print('查找结果:未查到')
展现结果
分别输入一个数据集中没有的数和数据集包含的数,两次结果展示如下: