行业知识
算法第三期——二分法(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万,只需要猜=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、猜数游戏代码
首先确定左端点和右端点,如果左端点= x: right = mid # 小于中间点则中间点作为右端点 else: # a[mid]
1.2、二分法的使用条件
- 上下界[a, b]确定
- 函数在[a,b]内单调
1.3、二分法的复杂度
- n次二分后,区间缩小到(b - a)/
- 给定a、b和精度要求,可以算出二分次数n,即满足(b -a)/=x时:x在mid的左边,新的搜索区间是左半部分,left不变,更新right = mid。
- a[mid]= x: right = mid # 小于中间点则中间点作为右端点 else: # a[mid]
结果:查找57,返回58 ;查找58,返回58
注意:若序列中存在多个x,会返回x第一次出现的下标
def bin_search1(a,n,x): l,r = 0,n while l=x: r=mid else: l=mid+1 return la = [1,2,2,3,5,5,5,6,7]print(bin_search1(a,len(a),5)) # 返回5第一次出现的下标:4
Python标准库:bisect_left() 两个参数:序列、目标值
# 找4from bisect import *a = [1,2,2,3,5,5,5,6,7]print(bisect_left(a,4))# import bisect# 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的左边,新的搜索区间是左半部分,所以left不变,更新right = mid -1。 - 代码执行完毕后,left = right,两者相等,即答案所处的位置。
代码演示(记忆)
def bin_search(a, n, x): left = 0 right = n while left
方法对比
整数二分例题:跳石头
题目来源:跳石头 - 蓝桥云课 (lanqiao.cn)
题目描述:
一年一度的"跳石头"比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M 块岩石(不能移走起点和终点的岩石)。
输入描述:
输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数 Di(0
-
下一篇:阿里云服务器怎么挂载?