算法第三期——二分法（Python）

目录

1、二分法

1.1、引导：猜数游戏

1.1.1、猜数游戏代码 

1.2、二分法的使用条件

1.3、二分法的复杂度

2、整数二分

2.1、在单调递增序列中查找x或者x的后继

求中间值的方法：

代码演示（记忆）

2.2、在单调递增序列中查找x或者x的前驱

求中间值的方法：

代码演示（记忆）

2.3 对比两种写法

二分法应用场景

二分的本质 

简易二分模板（推荐！不需要考虑前驱和后继）

整数二分例题：分巧克力

1、暴力法

2、二分法

方法对比 

整数二分例题：跳石头

二分法套路题:最小值最大化、最大值最小化 

代码演示

整数二分例题：青蛙过河 

思路： 

代码： 

3、实数二分

实数例题：一元三次方程求解 

【暴力法】求解

【二分法】求解

二分法难点

二分法习题

---

1、二分法

        在一个有序序列中查找某个元素，在之前我们可以使用暴力法来遍历序列，直至找到该元素，复杂度是O(n)，但其实可以利用序列有序的特征进行折半查找。
 二分法：把一个长度为n的有序序列上O(n)的查找时间，优化到了O(logn)。

• 二分法：折半搜索
• 二分的效率：很高，O(logn)
• 例如猜数游戏，若n= 1000万，只需要猜\(log_{2} 10^{7}\)=24次 

理论背景：非线性方程的求根问题

• 满足方程: f(x)=0的数x称为方程的根。
• 非线性方程:指f(x)中含有三角函数、指数函数或其他超越函数。很难或者无法求得精确解。二分法是一种求解的方法

1.1、引导：猜数游戏

 一个[1，100]内的数字，只需猜7次：
>50?是。[1，100]二分，中位数50，下一步猜[51,100]

>75?否。[51,100]二分，中位数75，下一步猜[51,75]

>63?否。[51,75]二分，...
>56?否。[51,63]二分，...

>53?是。
>54?否。

=54?是。这个数是54

【图解】：在1~10内找到7 

1.1.1、猜数游戏代码 

        首先确定左端点和右端点，如果左端点<右端点就一直循环，不断更新中间值mid = (right + left) // 2。如果目标点在左半区， 右端点往中间靠right = mid，如果目标点在右半区， 左端点往中间靠left = mid+1，直到循环结束，左端点或者右端点就是目标值。

1. def bin_search(a, n, x): # 在数组a中找数字x，返回位置
2. left = 0 # 二分法的左端点
3. right = n # 二分法的右端点
4. while left < right: # 右端点大于左端点则继续二分
5. mid = (right + left) // 2 # 折半前的中间点。//：整除
6. # mid = left + (right + left)//2 # C++有溢出问题，Python没有
7. if a[mid] >= x:
8. right = mid # 小于中间点则中间点作为右端点
9. else: # a[mid] < x,只是大于，所以要left = mid + 1
10. left = mid + 1 # 大于中间点则中间点作为左端点
11. print('[', left, right, ']') # 打印猜数的过程
12. return left
13. n = 100
14. a = [0] + [i for i in range(1, 101)] # #初始化1~100
15. test = 54 # #猜54这个数
16. pos = bin_search(a, n, test) # 二分搜索
17. print("test=", a[pos])

1.2、二分法的使用条件

• 上下界[a, b]确定
• 函数在[a,b]内单调

1.3、二分法的复杂度

• n次二分后，区间缩小到(b - a)/\(2^{n}\)
• 给定a、b和精度要求\(\xi\)，可以算出二分次数n，即满足(b -a)/\(2^{n}\)<\(\xi\)
• 二分法的复杂度是O(logn)。
• 例如，如果函数在区间[0,100000]内单调变化，要求根的精度是10-8，那么二分次数是44次 

2、整数二分

操作的序列中都是整数，如果处理不当可能陷入死循环。。。

2.1、在单调递增序列中查找x或者x的后继

        在单调递增数列a[ ]中查找某个数x，如果数列中没有X，找比它大的下一个数

求中间值的方法：

• mid = (left+right)//2
• mid = left+(right-left)//2

---

• a[mid]>=x时:x在mid的左边，新的搜索区间是左半部分，left不变，更新right = mid。
• a[mid]时:x在mid的右边，新的搜索区间是右半部分，right不变，更新left = mid + 1。
• 代码执行完毕后，left = right，两者相等，即答案所处的位置。 

代码演示（记忆）

1. # 查找57
2. def bin_search(a, n, x): # 在数组a中找数字x，返回位置
3. left = 0 # 二分法的左端点
4. right = n # 二分法的右端点 0~n-1:左闭右开[0,n)
5. while left < right: # 右端点大于左端点则继续二分
6. mid = (right + left) // 2 # 折半前的中间点。//：整除
7. if a[mid] >= x:
8. right = mid # 小于中间点则中间点作为右端点
9. else: # a[mid] < x,只是大于，所以要left = mid + 1
10. left = mid + 1 # 大于中间点则中间点作为左端点
11. return left
14. n = 200
15. a = [0] + [i for i in range(2, 202,2)]
16. test = 57
17. pos = bin_search(a, n, test) # 二分搜索
18. print("find =", a[pos]) # find = 58

结果：查找57，返回58 ；查找58，返回58 

注意：若序列中存在多个x，会返回x第一次出现的下标

1. def bin_search1(a,n,x):
2. l,r = 0,n
3. while l
4. mid = (l+r)//2
5. if a[mid]>=x:
6. r=mid
7. else:
8. l=mid+1
9. return l
11. a = [1,2,2,3,5,5,5,6,7]
12. print(bin_search1(a,len(a),5)) # 返回5第一次出现的下标:4

 Python标准库：bisect_left()                  两个参数：序列、目标值

1. # 找4
2. from bisect import *
3. a = [1,2,2,3,5,5,5,6,7]
4. print(bisect_left(a,4))
6. # import bisect
7. # print(bisect.bisect_left(a，4))

2.2、在单调递增序列中查找x或者x的前驱

        在单调递增数列al]中查找某个数x，如果数列中没有x，找比它小的前一个数

求中间值的方法：

• mid = (left+right+1)//2            # 这里需要+1
• mid = left+(right-left+1)//2

• ---

  a[mid] <=x时，x在mid的右边，新的搜索区间是右半部分，所以right不变，更新left = mid;
• a[mid]>x时，x在mid的左边，新的搜索区间是左半部分，所以left不变，更新right = mid -1。
•  代码执行完毕后，left = right，两者相等，即答案所处的位置。 

代码演示（记忆）

1. def bin_search(a, n, x):
2. left = 0
3. right = n
4. while left < right:
5. mid = (left+right+1)//2 # 不加上1会陷入死循环
6. if a[mid] <= x:left = mid
7. else: right = mid - 1
8. return left
11. n = 200
12. a = [0] + [i for i in range(2, 202,2)]
13. test = 57 # # 猜57或57的后继
14. pos = bin_search(a, n, test) # 二分搜索
15. print("find =v ", a[pos]) # find = 56

结果：查找57，返回56；查找56，返回56

注意：若序列中存在多个x，会返回x最后一次出现的下标

1. def bin_search2(a,n,x):
2. l,r = 0,n
3. while l
4. mid = (l+r+1)//2
5. if a[mid]<=x:
6. l = mid
7. else:
8. r = mid-1
9. return l
11. a = [1,2,2,3,5,5,5,6,7]
12. print(bin_search2(a,len(a),5)) # 返回5最后一次出现的下标:6

和Python标准库bisect_right()不同，bisect_right()返回的下标是应该插入的位置，例如目标值为4的话返回的是下标4，目标值为5的话默认插入在最后一个5后面。关系：bisect_right()比我们自己手写的代码bin_search2(a,n,x)返回的下标+1。

2.3 对比两种写法

注意下面红色标注部分

 二分法应用场景

1. 存在一个有序的数列上;
2. 能够把题目建模为在有序数列上查找一个合适的数值。

二分的本质 

        序列中的元素可以按某个规定的check()方法分为两个部分：一部分的check()为True，另一部分的check()为False。二分完成后，L和R分别指向所属区域的临界位置。（）

简易二分模板（推荐！不需要考虑前驱和后继）

假设：L指向check()=True的部分（≤目标值），R指向check()=False的部分（＞目标值），假设可以根据题目需要来确定。 

二分完成后，L和R分别指向所属区域的临界位置（终止条件:l+1=r）.
注意：左端点和右端点的初始化要定义在范围外，l, r = -1, n + 1

1. def check():
2. # 具体的check函数
3. pass
5. def bin_search(a, n, x):
6. l, r = -1, n + 1
7. while l + 1 != r:
8. mid = (l+r) // 2
9. if check(mid):
10. l = mid
11. else:
12. r = mid
13. return (l or r) # 选取需要的部分进行返回

举例：套用这个模板把区间划分成≤5和＞5两块，返回左边界：5的最后一个的下标。

1. # 把边界划分成≤5和＞5两块
2. def bin_search2(a,n,x):
3. l,r = -1,n # 左闭右开[0,n)：范围0~n-1
4. while l + 1 != r:
5. mid = (l+r)//2
6. if a[mid]<=x:
7. l = mid
8. else:
9. r = mid
10. return l # 返回左边界
12. a = [1,2,2,3,5,5,5,6,7]
13. print(bin_search2(a,len(a),5)) # 6

若想返回5的第一个的下标，把区间划分成＜5和≥5，返回右边界r。修改部分代码即可：

1. # 将上面的代码中间修改成这部分代码
2. if a[mid]>=x:
3. r = mid
4. else:
5. l = mid
6. return r # 返回右边界

---

整数二分例题：分巧克力

2017年第八届蓝桥杯省赛lanqi ao0J题号99

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi​×Wi 的方格组成的长方形。为了公平起见，

小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;

2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 N,K (1≤N,K≤10^5)。

以下 N 行每行包含两个整数Hi​,Wi​ (1≤Hi​,Wi​≤10^5)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

输入

1. 2 10
2. 6 5
3. 5 6

输出

2

切出的巧克力尽可能大，满足:(1）形状是正方形，边长是整数;(2）大小相同。 

1、暴力法

把边长从1开始到最大边长d，每个值都试一遍，一直试到刚好够分的最大边长为止。编码:边长初始值d=1，然后d=2.3,4,...一个个试。
复杂度：n个长方形，长方形的最大边长d。check()计算量是O(n)，做d次check()，总复杂度0(n* d)，n和d的最大值是\(10^{5}\)，超时。 

1. def check(d): # 检查够不够分
2. num=0 # 切成的份数
3. for i in range(n): # 遍历每一块巧克力
4. num += (h[i]//d)*(w[i]//d) # 将每一块巧克力切下来的份数进行统计。巧克力长宽要整除d哦！
5. if num>=k: # 够分
6. return True
7. else: # 不够分
8. return False
9. h = [0]*100010
10. w = [0]*100010
11. n,k = map(int,input().split())
12. for i in range(n):
13. h[i],w[i] = map(int,input().split())
14. d=1 # 正方形边长，从最小的边长开始试
15. while True:
16. if check(d):
17. d+=1 # 边长从1开始，一个个地暴力试
18. else: # 当前的d不满足，所以下面输出的时候d要-1（前一个d满足）
19. break
20. print(d-1)

2、二分法

        一个个试边长d太慢，用二分，按前面的“猜数游戏”的方法猜d的取值，因为d从小到大是一个有序数列。

暴力法需要做d次eheck();二分法只需要做O(ogd)次eheck()，总复杂度O(nlogd)。

1. def check(d):
2. num = 0
3. for i in range(n):
4. num += (w[i] // d) * (h[i] // d)
5. if num >= k:
6. return True
7. else:
8. return False
9. h = [0] * 100010 # 边界最好比题目要求的大一点，避免边界上出了问题
10. w = [0] * 100010
11. n, k = map(int, input().split())
12. for i in range(n):
13. h[i], w[i] = map(int, input().split())
14. L, R = 1,100010
15. while L < R:
16. mid = (L + R) // 2
17. if check(mid): # 数量满足要求就把左端点提高到中间点
18. L = mid + 1
19. else: # 数量不满足要求就把右端点降低到中间点
20. R = mid
21. print(L - 1)

上面代码有点麻烦，用简易二分模板来写： 

1. def check(d):
2. num = 0
3. for i in range(n):
4. num += (w[i] // d) * (h[i] // d)
5. if num >= k:
6. return True
7. else:
8. return False
9. h = [0] * 100010 # 边界最好比题目要求的大一点，避免边界上出了问题
10. w = [0] * 100010
11. n, k = map(int, input().split())
12. for i in range(n):
13. h[i], w[i] = map(int, input().split())
14. L, R = 0,100010
15. while L + 1 != R:
16. mid = (L + R) // 2
17. if check(mid): # 数量满足要求就把左端点提高到中间点
18. L = mid
19. else: # 数量不满足要求就把右端点降低到中间点
20. R = mid
21. print(L)

方法对比 

整数二分例题：跳石头

题目来源：跳石头 - 蓝桥云课 (lanqiao.cn)

题目描述：

一年一度的"跳石头"比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M 块岩石（不能移走起点和终点的岩石）。

输入描述：

输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 N 行，每行一个整数，第 i 行的整数 Di​（0第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

其中，0≤M≤N≤5×10^4，1≤L≤10^9。

输出描述：

输出只包含一个整数，即最短跳跃距离的最大值。

输入输出样例：

输入

1. 25 5 2
2. 2
3. 11
4. 14
5. 17
6. 21

输出

4

二分法套路题:最小值最大化、最大值最小化 

        在n块岩石中移走m个石头，有很多种移动方法。在第i种移动方法中，剩下的石头之间的距离，有一个最小距离ai。在所有移动方法的最小距离ai中，问最大的ai是多少？在所有可能的最小值中，找最大的那个，就是“最小值最大化。

• 暴力法：找所有的组合，在n块岩石中选m个石头的组合\(C_{n}^{m}\)。情况太多，显然会超时...
• 二分法：不去找搬走石头的各种组合，而是给出一个距离d，检查能不能搬走m块石头而得到最短距离d。把所有的d从小到大都试一遍，肯定能找到一个最短的d。用二分法找这个d即可。

代码演示

 用二分法找一个最小距离d。函数check(d)函数检查d这个距离是否合适。

函数check(d)：检查距离d是否合适（贪心法）
        把前后两块石头距离＜d，将第i块石头（两块之间较后一块）搬走，前后两块石头距离≥d的留下 ，并将位置从前一块转移到第i块（后一块），如果移走的石头不超过m块，则返回True，可以提高距离d，如果移走的石头超过m块，不符合题意，则返回False，应该减小距离d。

【图解】：把前后两块石头距离＜d，不满足最小距离的要求，所以pos不变，stone[i+1],相当于将第i块石头（两块之间较后一块）搬走，下次还是比较从原来pos开始到stone[i+1]这段距离。（pos不变则认为是同一段距离）

 【图解】：前后两块石头距离≥d的留下 ，因为当前距离满足≥最小距离d，所以并将位置pos从前一块转移到第i块（两块之间较后一块），准备比较下一段距离。

1. def check(d):
2. num = 0 # num：最终移走的石头数
3. pos = 0 # 起点坐标
4. for i in range(0, n): # 0到n-1作为石头下标
5. if stone[i] - pos < d: # 后面的石头距离位置pos的距离＜d，第i块可以搬走
6. num += 1
7. else: # 当后面石头距离位置pos的距离≥d，不能搬走，
8. pos = stone[i] # 位置pos变成后面的石头
9. if num <= m: # 不超过上限m块(最多移走m块)，符合题意，可以增大距离d
10. return True
11. else: # 移走超过m块石头，不合题意，应该减小距离d
12. return False
13. len, n, m = map(int, input().split())
15. stone = []# 第i块石头到起点的距离
17. # 读入每块石头与起点的距离
18. for i in range(n):
19. t = int(input()) # 也可以不用t,直接stone.append(int(input)))
20. stone.append(t)
22. # 二分法找最小距离d
23. L, R = 0, len # 确定左右端点
24. # 只能查找x或者x的前驱，不能找后继，因为后继就不是最小值了
25. while L < R: # 这部分只套用二分法的前驱写法
26. mid = (L + R +1) // 2
27. if check(mid): # 将左端点提高到中点
28. L = mid
29. else:
30. R = mid - 1 # 将右端点减小到中点
31. print(L)

用简易二分模板来写： 

1. def check(d):
2. num = 0 # num：最终移走的石头数
3. pos = 0
4. for i in range(0, n): # 0到n-1作为石头下标
5. if stone[i] - pos < d: # 后面的石头距离位置pos的距离＜d，第i块可以搬走
6. num += 1
7. else: # 当后面石头距离位置pos的距离≥d，不能搬走，
8. pos = stone[i] # 位置pos变成后面的石头
9. if num <= m: # 不超过上限m块(最多移走m块)，符合题意，可以增大距离d
10. return True
11. else: # 移走超过m块石头，不合题意，应该减小距离d
12. return False
13. len, n, m = map(int, input().split())
15. stone = []# 第i块石头到起点的距离
17. # 读入每块石头与起点的距离
18. for i in range(n):
19. t = int(input()) # 也可以不用t,直接stone.append(int(input)))
20. stone.append(t)
22. # 二分法找最小距离d
23. L, R = -1, len + 1 # 确定左右端点
24. # 只能查找x或者x的前驱，不能找后继，因为后继就不是最小值了
25. while L +1 != R: # 这部分只套用二分法的前驱写法
26. mid = (L + R) // 2
27. if check(mid): # 将左端点提高到中点
28. L = mid
29. else:
30. R = mid # 将右端点减小到中点
31. print(L)

整数二分例题：青蛙过河 

 2022年第十三届蓝桥杯省赛,lanqiao0J题号2097

问题描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 天课。

输入格式

输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。

第二行包含 n−1 个非负整数 H1​,H2​,⋯,Hn−1​, 其中 Hi​>0 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 Hi​ 的石头, Hi​=0 表示这个位置没有石 头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例输入

1. 5 1
2. 1 0 1 0

样例输出

4

样例说明

由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

评测用例规模与约定

对于 30% 的评测用例, n≤100;

对于 60% 的评测用例, n≤1000;

对于所有评测用例, 1≤n≤10^5,1≤x≤10^9,1≤Hi​≤10^4 。

思路： 

• 往返累计2x次相当于单向走2x次。
• 跳跃能力越大，越能保证可以通过2x次。
• 用二分法找到一个最小的满足条件的跳跃能力。
• 设跳跃能力为mid，每次能跳多远就跳多远，用二分法检查mid是否合法。

        题目要求的是能上完学的最小的跳跃能力，所以我们可以想到用二分法来找出最小跳跃能力，定义check()函数来判断能否上完学。难的是check函数 首先想一个必要条件，如果check(y)返回True，那么对于所有以i开始长度为y的区间，区间中所有数之和必然不少于2x。可以想象，因为最多跨y个长度，因此来回肯定都要经过这个区间，这个区间肯定要能被踩至少2x次 这个条件也是充分条件，因为如果所有长度为y的区间都能至少踩2x次，那么肯定能够完成2x次来回。 

【图解】例如看下面的图，起点和终点之间有若干个长度为mid的区间，若青蛙的跳跃能力＝mid，这每到对岸一次，都必须经过每个区间，那么来回就是必须经过每个区间两次，上学x天就应该经过2x次每个区间2x次，如果区间内石头高度和小于2x（不能踩2x次），则不能上完学，应该提高跳跃能力，如果区间内石头高度和≥2x，则可以上完学，减少跳跃能力以找到最低跳跃能力。

        上面的区间是从起点开始，长度为y的区间，但其实这是不充分的，因为所有区间向右移动1个位置后，所有区间的是新的区间（区间内的石头高度变了），这些新的区间也需要满足区间内石头高度和≥2x。当所有长度为mid的区间都能至少踩2x次，那么肯定能够完成2x次来回。

代码： 

1. def check(mid):
2. for i in range(mid,n):
3. if sum[i] - sum[i-mid] < 2*x: # 长度为mid的区间和＜2x
4. return False # 跳不过去
5. return True # 全部区间长度都≥2x，则能跳过去
6. n, x = map(int, input().split())
7. h = list(map(int, input().split()))
8. sum = [0,h[0]]
9. for i in range(1, len(h)):
10. sum.append(h[i] + sum[i])
11. L=0
12. R =100000
13. while L +1 != R:
14. mid=(L+R) //2
15. if check(mid): R = mid # 能跳过去，减少跳跃能力
16. else: L = mid # 不能跳过去，提高跳跃能力
17. print(R) # 能跳过去的最小跳跃能力

3、实数二分

与整数二分法相比，实数二分容易多了，不用考虑整数的取整问题。
两种写法: while、for 

1. eps = 0.00001 #精度
2. while right - left > eps: # 区间＞精度，说明达不到精度值，继续二分
3. mid = (left+right)/2 # 实数二分的话这里是/，整数二分是//
4. if check(mid): #判定
5. right = mid
6. else:
7. left = mid

1. for i in range(100): # 做100次二分，精度：1/2^100
2. mid = (left+right)/2#判定
3. if check(mid):
4. right = mid
5. else:
6. left = mid

实数例题：一元三次方程求解 

题目描述

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在 −100 至 100 之间)，且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。

提示：记方程 f(x)=0，若存在 2 个数 x1​ 和 x2​，且x1​

输入描述

输入一行，4 个实数 a,b,c,d。

输出描述

输出一行，3 个实根，从小到大输出，并精确到小数点后 2 位。

输入输出样例

输入

1 -5 -4 20

输出

-2.00 2.00 5.00

【暴力法】求解

• 本题数据范围小，可以用暴力法模拟。
• 元三次方程有3个解，用暴力法，在根的范围[-100,100]内一个个试，因为两个之间距离≥1，所以分成两百个小区间，一个区间内部最多只能有一个解。答案只要求3个精度为2位小数的实数，那每个小区间再分成100份，精度为0.01。那么只需要试200*100 = 20000次就行了。
• 判断一个数是解的方法:如果函数值是连续变化的，且函数值在解的两边分别是大于0和小于0，那么解就在它们中间。例如函数f（i）和f（j）分别大于、小于0，那么解就在[i，j]内。

 【二分法】求解

如果题目要“精确到小数点后6位”，上面的暴力法需要计算200*\(10^{6}\)次，超时了

二分法:题目给了一个很好的条件: 根与根之差的绝对值大于等于1。那么所有的[i,i+1]小区间（200个小区间）内做二分查找就行。

1. def y(x): return a*x*x*x+b*x*x+c*x+d
3. a,b,c,d = map(float,input().split()) # 不能用int，因为输入有浮点数。
4. # n = input().split()
5. # a,b,c,d = eval(n[0]),eval(n[1]),eval(n[2]),eval(n[3]) # eval 将字符串转成对应数值（整型、浮点型...）
6. for i in range(-100,100):
7. left,right=i,i+1 # 在每个[i,i+1]小区间内做二分
8. y1,y2=y(left),y(right) # 计算区间端点的值
9. if y1==0: # y1==0就是解
10. print("{:.2f}".format(left),end=" ") # 注意输出格式：保留两位小数
11. if y1*y2<0: # 在这区间内有解
12. #while (right-left) >= 1e-10: #精确到小数点后两位小数，要往后多求几位
13. for i in range(100): # 100次二分：在这个区间内求解
14. mid =(left+right)/2
15. if y(mid)*y(right) <=0: left = mid
16. else: right = mid
17. print("{:.2f}".format(right),end=" ")

二分法难点

1. 要把题目信息建模为可以使用二分法解决的问题，二分法可以解决一般最值问题。
2. 怎么写一个check函数（根据题目要求）
3. 二分法本身取整的问题（参考上面介绍过的整数二分）。如果用的是简易二分模板其实这里不需要考虑这个

二分法习题

可以在蓝桥杯官网：题库 找到下面这些题目

  本文参考罗勇军老师的蓝桥云课