打开《Python入门与实战》_一步步学会Python_5.2.2.1 二分查找法

【摘要】 本书摘自《Python入门与实战》一书中第5章，第2节，由王跃进主编。

5. 二分查找法

算法分析：二分查找也称折半查找，是一种效率较高的查找方法。但它仅适用于 已经排好序的序列。其基本思路是：首先将给定值 K 先与序列中间位置元素比较，若 相等，则查找结束；若不等，则根据K 与中间元素的大小，确定是在前半部分还是后 半部分中继续查找。这样逐渐缩小范围进行同样的查找。如此反复，直到找到(或查 找范围的长度为0)为止。

我们来模拟前面的猜数游戏，实现代码：

01 import random

02 total=0

03 expr=["甲得意地说：","甲做了个鬼脸说：","甲高高蹦了一下说："]

04 def search(li,k):

05 """二分法查找"""

06 global total

07 total+=1

08 mid=len(li)// 2

09 if len(li)>0:

10 if k ==li[mid]:

11 print("乙猜的数：",li[mid],"甲低下头，小声说：猜中了")

12 reuTue

13 elif k

14 print("乙猜的数：",li[mid],expr[random.randrange(0,len(expr))]+"大了")

15 return search(li[:mid],k)

16 else:

17 print("乙猜的数：",i[mid],expr[random.randrange(0, len(expr))]+"小了")

18 return search(li[mid+1:],k)

19 else:

20 return False

21 li =[i for i in range(1,1000)]

22 answer = random.randrange(1,1000)

23 print("甲想的数：",answer)

24 search(li,answer)

25 print("共：",total,"次")

5.2.6 动手实践

(1)现有列表 numlist=[3,2,14,18,88,34,76,9,10], 请计算列表的最大跨度值(最大

跨度值=最大值-最小值)。

分析：要求列表的最大跨度值，必须先求出列表元素的最大值和最小值，因此必

须遍历列表。对列表进行两次遍历，分别求出最大值和最小值。代码如下：

numlist=[3,2,14,18,88,34,76,9,10]

02 maxvalue =numlist[0]

03 minvalue = numlist[0]

04 for item in numlist:

05 if item>maxvalue:

06 maxvlue =item

07 for item in numlist:

08 if item

09 minvalue=iten

10 span = maxvalue- minvalue

11 print(span)

在上面的代码中对列表进行了2 次遍历，如果列表很长，消耗在遍历列表的时间 也会很长，如果实际问题对运行时间有严格要求，我们需要设计出尽可能优雅的代码 下面是改进的代码：

01 numlist =[3,2,14,18,88,34,76,9,10]

02 maxvalue = numlist[0]

03 minvalue = numlist[0]

04 for item in numlist:

05 if item> maxvalue:

06 maxvalue = item

07 if item

08 minvalue = item

09 span = maxvalue- minvalue

10 print(span)

通过改进后，对列表只进行1 次遍历即可得出最大值和最小值，从而大幅度地缩 短了运行时间。仔细分析程序运行过程，我们可以对07行代码稍加修改还可以进一步 缩短程序运行时间，你知道怎么修改吗?

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 [email protected] 处理，核实后本网站将在24小时内删除侵权内容。