小工具知识网

当前位置: 首页 > 行业知识 > 【算法】—二分法详解

行业知识

【算法】—二分法详解

2026-11-21 00:18:26 来源:互联网转载

二分法

文章目录

  • 二分法
    • 1.二分法
    • 2.引论:猜数游戏
    • 3.整数域二分
      • 1、在单调递增序列中找 x 或者 x 的后继
      • 2、在单调递增序列中查找 x 或者 x 的前驱
      • 3.简易二分模板
      • 4.浮点数二分
      • 5.边界二分
        • 1.旋转数组
        • 2.开闭区间
        • 6.二分法的应用
          • 1.优化时间复杂度
          • 2.最小值最大化
          • 3.最大值最小化
          • 7.���结

            1.二分法

            ①定义:二分查找算法也称折半搜索算法,对数搜索算法,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半,时间复杂度是log(n)

            • 一是有序数组(这里可能是整体有序比如[1,2,3,4,5],也有可能是局部有序比如[4,5,1,2,3]),
            • 二是特定元素(也有可能是满足特定的条件)。由定义我们大概就知道了二分法的应用场景,在有序数组中找特定值都可以考虑用二分法

              ②二分法的步骤:

              我们要确定一个区间[L,R]我们要找到一个性质(由题目条件决定),并且该性质满足一下两点: ①满足二段性 ②答案是二段性的分界点

              我们要在一组升序的数组找一个数的下标,那我们肯定是先拿中间的与他进行比较,比较大小的判断,其实就相当于是这个性质,且这个性质满足二段性,将大于和小于我们要查找的值分为两段,而我们的查找结果就是分界点

              ③二分法的使用条件:

              ①上下界确定 ②区间内有序(也可以是局部有序)

              ④二分法的目的:

              二分查找用于在多条记录中快速找到待查找的记录,它的思想是:每次将查找的范围缩小一半,直到最后找到记录或者找不到记录返回

              2.引论:猜数游戏

              示例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

              模板:

              def bin_search(nums)low, high = 0, len(nums) - 1        while low  target:                high = mid - 1            else:                low = mid + 1        # 未找到目标值          return -1

              思路分析:

              二分法题目都可以分下面三步:

              1. 确定是否满足二分法的使用条件 ,有序数组与查找特定元素,题目中a有序,查找的是指定元素test,满足条件
              2. 确定特定元素test,如:a[pos]=test
              3. 确定边界的变化,根据定义的第二句话,写出代码如下

              3.整数域二分

              m i d = ( l e f t + r i g h t ) / / 2 mid = (left+right) // 2 mid=(left+right)//2

              m i d = l e f t + ( r i g h t − l e f t ) / / 2 (防止溢出) mid = left + (right-left) // 2 (防止溢出) mid=left+(right−left)//2(防止溢出)

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

              • 在单调递增数列 a[ ] 中查找某个数 x,如果数列中没有 x,找比它大的下一个数
              • a[mid]>=x 时:x 在 mid 的左边,新的搜索区间是左半部分,left不变,更新 right= mid
              • a[mid]

上一篇:私服怎么上传服务器

下一篇:单片机数据上传到云端服务器中怎么办