Python 算法 01–二分查找

大家好，欢迎来到IT知识分享网。

猜数游戏

在程序中预设一个 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)

注意：仅当列表是有序的时候，二分查找才管用

>>>Python算法 00–时间复杂度和空间复杂度