小工具知识网

当前位置: 首页 > 行业知识 > 算法第三期——二分法(Python)

行业知识

算法第三期——二分法(Python)

2026-11-18 00:39:17 来源:互联网转载

���录

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

上一篇:随拍,定格瞬间之美,记录生活精彩瞬间

下一篇:阿里云服务器怎么挂载?