Python语言实现二分法查找

前言：

二分法也就是二分查找，它是一种效率较高的查找方法

假如公司新来了一个人，叫张三，他是你们公司第47个人，过了一段时间后，有些人呢看张三不爽，离职了，那这时候张三肯定不是公司第47个人了，怎么样才知道张三排第几呢，下面我们用二分法把他找出来

思路：

给你一本1000页的书籍，随机给定一个页码，如何用最快的方式找到它？如果一页一页逐步去查找，则最高需要查找一千次！那我们如何用二分法来解决这个问题呢？二分法的关键就是二分这个词。

 

 步骤1： 设定一个页码作为中心点来将1000页分为两份，中位数的作用就是每次缩小一半查找范围，即达到开方的效果。即可以用 (首位+末位)/2 = 中位数。

 步骤2： 将需要查找的页码与中位数比价,如果大于中位数则舍弃对中位数的前一半查找，反之则舍弃对后一半范围查找，达成开方效果。 步骤3：在新的查找范围重新计算出中位数 

步骤4： 查找页码对比中位数，确定新的查找范围

步骤5： 循环以上步骤，直到找到该页码为止

代码：

通过以上思路解析,我们知道了二分法实行步骤,接下来就通过代码来实现步骤，首先是循环实现

#模拟页码
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#设定查找页码
findNum = 1
?
#循环查找
while True:
? ? #获取中位数
? ? mid = int((low+height)/2)
? ? #打印中位数,查看循环次数
? ? print(array[mid])
? ? #如果中位数小于查找值,则锁定后半段
? ? if array[mid] < findNum:
? ? ? ? #重置低位数
? ? ? ? low = mid + 1
? ? #如果中位数大于查找值,则锁定前半段
? ? elif array[mid] > findNum:
? ? ? ? #重置高位值
? ? ? ? height = mid - 1
? ? #找到数字则打印该值下标,终止循环
? ? elif array[mid]==findNum:
? ? ? ? print('find it:',array[mid],' index:',mid)
? ? ? ? break

除了上述方式外,也可以使用递归来实现,代码更加简洁

array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
?
#函数递归
#定义一个函数,给三个形参:低位值，高位值，查找值
def BinarySearch(low,height,findNum):
? ? #计算出中位数
? ? middle = (low+height)//2
? ? #如果中位数小于查找值,则锁定后半段
? ? if findNum >array[middle]:
? ? ? ? #重置低位数
? ? ? ? low = middle +1
? ? #如果中位数大于查找值,则锁定前半段
? ? elif findNum<array[middle]:
? ? ? ? #重置高位值
? ? ? ? height = middle - 1
? ? else:
? ? ? ? #找到该值并返回
? ? ? ? return '该值下标为:%s,值为:%s'%(middle,array[middle])
? ? #没有找到则调用自身继续查找
? ? return BinarySearch(low,height,findNum)
?
print(BinarySearch(array[0],len(array)-1,19))

总结：

根据结果反馈，使用二分法常规Python检索用循环方式找数字21，他是排在11位，中位数查询3次，使用Python二分法检索递归方式先取查询数字的倍数，然后锁定前半段进行索引,索引的步骤耗时更少

到此这篇关于Python语言实现二分法查找的文章就介绍到这了,更多相关Python二分法查找内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

查看更多关于Python语言实现二分法查找的详细内容...