| title | date | tags | summary | ||
|---|---|---|---|---|---|
算法——二分查找 |
2021-08-28 |
|
当时那个红包的数字离我就只有一数之遥，如果上天能给我一次重来的机会的话，我会用二分查找算法来重新玩这个猜数字的游戏…… |
今天回老家，参加了好基友的婚宴，饭菜很丰盛，气氛很热烈，新郎官也帅气（这句话五毛，发的时候记得删掉括号。席间主持人玩的一个猜数字的游戏，引发了我如下的一些思考……
先简单介绍下，猜数字的游戏规则。规则特别简单，每个红包上面都有一个数字，主持人说出数字的范围，然后每个席位轮流给出猜测的数字，如果猜测的数字命中红包上的数字，那么恭喜你，红包是你的了。如果没命中，司仪会给出这个数字是大了还是小了，让下一桌的人接着去猜，直到有人猜中。
身为一个放荡不羁不加班的程序猿，总会想着有没有什么又好又快的解决方法，这样我也能不惦记红包，好好吃点菜了。在算法里面，有一个特别简单的算法，就是解决这类问题的最大杀器——二分查找（Binary Search）。
二分查找又称为折半查找，它是一种效率很高的查找方式，只是程序设计中，它必须用于有序排序的线性结构中。
在刚刚这个猜数字的游戏里面，数字是连续的，而且也是从低到高有序的。假如司仪说数字范围从0到100，那么就是有序序列 0 ~ 100，这里用二分查找，最倒霉的情况只需要猜 7 次，也就是说，这个范围可以被折半7次，可以从 (2^7 = 128) >= 100 推导出来。
ok，假定司仪每次都是 [1, 100] 这个区间让人去猜，不用算那么麻烦，单单从高效地猜中数字，快速开启下一把这个角度看，也能提升中奖率了吧。
通过给定的区间，每次都猜区间中的中位数，不断地缩小区间的范围，折半又折半，逼近猜测的数字。理论上 2^n 个数，最多只要猜 n 次就能命中。
def binary_search(List, target):
lo = 0
hi = len(List) - 1
while lo <= hi:
mid = (hi + lo) // 2
if target > List[mid]:
# 猜测的数字小了
lo = mid + 1
elif target < List[mid]:
# 猜的数字大了
hi = mid - 1
else:
# 猜中了，返回下标
'bingo'
return mid
# 结束了还没找到就返回None
return None 当然，席上其他人很多都不是程序猿，估计也没想过这个小小问题，所以经常给出的数字都是枚举式的，即从1到100挨个地猜。
def jsut_guest_num(List, target):
idx = 0
while idx < len(List) :
if List[idx] == target:
return idx
idx += 0
else:
return None这种肯定也能猜中，只要时间够久，就是有点费菜。哈哈，最后本人一无所获，我女票秉持着，大喜日子，数字应该有6有8，然后应该还是双数（好事成双嘛），各种猜测，拿了个红包。
最后，祝东哥枫姐新婚快乐，日子红红火火。