Python 算法 01--二分查找
猜数游戏
在程序中预设一个 0-9 之间的整数，让用户通过键盘输入所猜的数，
如果大于预设的数，显示 “遗憾，太大了”；小于预设的数，显示 “遗憾，太小了”
如此循环，直至猜中该数，显示 “预测 N 次，你猜中了！”，其中 N 是用户输入数字的次数
1、Python 分析
● “预设一个 0-9 之间的整数” 可以使用 random 库中的 randint 函数
注意：randint (a,b) 区间是包含 a 和 b 的，而 range 函数左闭右合
● 用户键盘输入数字，使用 eval(input())
● 在确定循环次数时，我们用 for 循环，在不确定的时候用 while 循环
● 显示 “预测 N 次，你猜中了！”, 其中 N 可以使用 format 函数格式化
2、Python 代码
3、策略
● 简单查找：从 1 开始依次往上猜
每次猜测只能排除一个数字，如果数字是 100，那从 1 - 100 需要猜 100 次
● 二分查找：每次猜测中间的数字
在未猜测正确前，每次猜测都将余下的数字排除一半。
二分查找
数组list
● low 和 high 表示数组 list 的开始和结束
low = 0 # 数组开始
high = len(list) - 1 # 数组结束
● 只要范围没有缩小到只包含一个元素，就检查中间的元素
● 中间元素
mid = (low + high) // 2
如果 low + high 不是偶数，Python中// 向下取整
● Python 二分查找代码
● 二分查找的时间复杂度
当第 K 次查找到元素，N/(2^K) >= 1
我们计算时间复杂度是按照[最坏的情况]进行计算
所以二分查找的时间复杂度是log N (默认 log 的底数是 2)
注意：仅当列表是有序的时候，二分查找才管用