从猜数游戏到二分查找算法
不点蓝字，我们哪来故事？
往期推荐
点击标题即可阅读
）
今天我们一起用python写一个猜数游戏。先来看看现实生活中我们是什么玩法。首先我们需要在大脑中假定一个数字，当然这个数需要有一个范围，比如1到100，然后让对方去猜这个数字，如果数字大于或者小于目标数字就给出相应的提示，直到对方猜出数字，游戏结束。
01
先来写个猜数游戏.
下面我们按照这个流程图来实现这个程序。按照惯例，我们先用scratch试一下。
你用几次能猜到这个数捏？游戏如果没有挑战性，也就失去了它的趣味。所以我们需要在上面的程序中，稍作修改，增加次数限制。
python程序又该如何实现呢？
import random
import time
print('猜数字游戏：随机抽取一个1～100内的秘密数字，猜对了游戏结束')# 打印游戏提示
time.sleep(1)
print('不过，你只有5次机会哦～')
time.sleep(1)
secret_number = random.randint(1, 100) # 生成秘密数字
times = 5 # 设置游戏可猜次数
# 直到猜数字次数用完之前，循环
while times:
times -= 1 # 执行一轮猜测消耗一次猜数次数
guess=int(input('你猜的数字是：'))
time.sleep(0.5)
if guess > secret_number :# 当猜测值比秘密数字大时的提示
print('比秘密数字大！(＞﹏＜)～～')
elif guess < secret_number:# 当猜测值比秘密数字小时的提示
print('比秘密数字小!（´д｀）ゞ。。。。')
# 猜中时的提示，并且结束游戏
else:
print('你猜对啦!秘密数字是:{}，你猜了{}次就猜到了(^_^)～～～'.format(secret_number,5-times))
break
# 当次数剩下一次的提示
if times == 1:
time.sleep(0.8)
print('最后一次机会啦！猜不到就公布答案')
# 猜不中的提示
elif times == 0:
time.sleep(0.8)
print('你有5次机会，可惜你没有珍惜！正确答案是：{}!'.format(secret_number))
time.sleep(0.8)程序中用了random模块，用于生成随机数，random.randint(1, 100)生成了一个1到100之间的整数。time模块，time.sleep(0.8)产生一个以秒为单位的时间间隔。为什么循环条件是 while times: 在python中像while 1, while 2, while -1, while -2, while x, 只要不等于0, 就是条件永远为真, 等价于while True，while 0 等价于 while False。所以循环的条件就是times不等于0。
程序最重要的是要严谨，如果用户不按套路出牌，输入了大于100的数，或者直接输入字符而不是数字呢，程序是不是也应该做出一些回应？这就是异常。我们在程序开发的时候，很难将所有的特殊情况都处理，通过异常捕获可以针对突发事件做集中处理，从而保证程序的健壮性和稳定性。
在程序开发中，可以增加try来捕获异常。
try:尝试执行的代码
except:出现错误的处理
try:
guess = int(guess)
if guess < 1 or guess > 100:
raise ValueError
# 报错时输出提示
except ValueError:
print('\n请输入一个1~100的数字哦！')接下来，给出完整的代码：
import random
import time
print('猜数字游戏：随机抽取一个1～100内的秘密数字，猜对了游戏结束')# 打印游戏提示
time.sleep(1)
print('不过，你只有5次机会哦～')
time.sleep(1)
secret_number = random.randint(1, 100) # 生成秘密数字
times = 5 # 设置游戏可猜次数
# 直到猜数字次数用完之前，循环
while times:
times -= 1 # 执行一轮猜测消耗一次猜数次数
guess=input('你猜的数字是：')
time.sleep(0.5)
try:
guess = int(guess)
if guess < 1 or guess > 100:
raise ValueError
# 报错时输出提示
except ValueError:
print('\n请输入一个1~100的数字哦！')
else:
if guess > secret_number :# 当猜测值比秘密数字大时的提示
print('比秘密数字大！(＞﹏＜)～～')
elif guess < secret_number:# 当猜测值比秘密数字小时的提示
print('比秘密数字小!（´д｀）ゞ。。。。')
# 猜中时的提示，并且结束游戏
else:
print('你猜对啦!秘密数字是:{}，你猜了{}次就猜到了(^_^)～～～'.format(secret_number,5-times))
break
# 当次数剩下一次的提示
if times == 1:
time.sleep(0.8)
print('最后一次机会啦！猜不到就公布答案')
# 猜不中的提示
elif times == 0:
time.sleep(0.8)
print('你有5次机会，可惜你没有珍惜！正确答案是：{}!'.format(secret_number))
time.sleep(0.8)你5次之内能猜到这个数吗？我试了一下，好像有点难度，这是我猜数的过程。
02㏒
开个外挂，二分查找法.
你的目标是以最少的次数猜到这个数字。假设你从1开始依次往上猜，那么你每次只能排除一个数字，这种方法就是通俗的傻找法，如果这个数是100，你就需要找100次。
下面是一种更佳的猜法，从50开始，如果小了，你知道1--50都小了，接下来你猜75，大了，50--75都大了，余下的数字又排除了一半。这种搜索算法每一次比较都使搜索范围缩小一半。这就是二分查找法，这是一种算法。
不管你心里想的是哪个数字，1--100的一个数，你最多7次，都能猜到它。
一般来说，对于包含n个元素的列表，用二分查找法，最多需要步。如果让你猜一个1--1000的数，需要
，也就是10次。需要说明的是，仅当列表有序的时候，二分查找才有用。
下面看看如何写出用二分查找法猜数的python代码。
import random
secret_number = random.randint(1, 1000) # 生成秘密数字
lis=list(range(1,1001))
low=0
high=len(lis)-1
n=0
while low<=high: #直到范围缩小到一个元素
mid=(low+high)//2 #取中间值，向下取整,将索引赋值给mid
guess=lis[mid]#在列表中找到这个数
print(guess,end="\t")
n+=1
if guess==secret_number:
print("\n我猜到这个数了，它是：{}。我猜了{}次".format(guess,n))
break
if guess>secret_number:
high=mid-1
else:
low=mid+1
print("秘密数字是:{}".format(secret_number))来吧，展示。
如果要猜的数字是1--40亿，需要多少次呢?答案是最多猜32次，这也太厉害了吧，感觉像开了外挂。二分查找的运行时间为对数时间。
和你的小伙伴用二分查找法玩猜数游戏吧，注意尽量让他想的数大一点，再大一点。
我们就擦肩而过了
有趣
有用
有态度