使用Python实现二分法查找的示例
关于二分法的定义我就不说了,CSDN很多大牛和前辈都已经阐述的很清楚了,直接上代码。
首先,先创建一个名称为 binary_search 的函数:传递两个参数,元素列表和要查找的值。
def binary_search(_list, value):
接下来,在函数内部定义所需的变量,二分法的关键在于从列表的中间向两侧查找(表述可能不严谨,大概这个意思),所以为了直观起见,定义 left,right, mid 三个变量,分别代表:列表的起始索引,结束索引和中间索引。
left = 0 # 列表的起始索引 right = len(_list) # 列表的结束索引 mid = int((left + right)/2) # 采用此方法,通过四舍五入刚好可以定位到列表的中间位置
接下来是实现二分查找的关键部分,先定义一个while循环,使得查找可以顺利进行,while函数内嵌套 if 分支语句实现条件判断,共有三种情况:
1. _list[mid] == value: 中间值恰好是我们需要查找的值,那么直接返回对应的索引就可以了。
2._list[mid] > value: 要查找的值在mid的左侧,更新right 的值为mid,缩小查找范围。
3._list[mid] <value:要查找的值在mid的右侧,更新left的值为mid,到 mid 右侧进行查找。
最后,对mid的值做一下更新,以便开始下一轮查找,同时采用 while-else语句针对没有查找到的情况进行判断,并给定一个返回值。
while left < right: if _list[mid] == value: return mid elif _list[mid] > value: right = mid else: left = mid mid = int((right + left)/2) else: return -1
最后,完整代码,以及测试运行表现如下:
""" a demo realize binary search""" def binary_search(_list, value): left = 0 # 列表的起始索引 right = len(_list) # 列表的结束索引 mid = int((left + right)/2) # 采用此方法,通过四舍五入刚好可以定位到列表的中间位置 while left < right: if _list[mid] == value: return mid elif _list[mid] > value: right = mid else: left = mid mid = int((right + left)/2) else: return -1 index = "the index of value in the list: {}" print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))
运行结果:
没有要查找的值的情况:
关于使用Python实现二分法查找的示例的文章就介绍至此,更多相关Python实现二分法查找内容请搜索编程宝库以前的文章,希望以后支持编程宝库!
为什么需要线程间通信一个人的力量是有限的,但是团队合作可以发挥更大的作用。而团队协作需要交流和通信来有效的分配任务和协调工作,来保证保时保量的完成工作。为什么线程间需要通信呢?这就好比一个团 ...