草庐IT

二分

冒泡儿 2023-03-28 原文

1.整数二分

用一个性质将区间分为满足性质和不满足性质，答案是二分的边界

情况一

代码分析
int bsearch_1(int l,int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; //如果mid满足性质缩小区间为[l,mid]
        else l = mid + 1; //如果mid不满足性质缩小区间为[mid+1,r]
    }
    return l;
}
//最后输出l或r都行，因为二者相等

如果[l,r]中没有ans那么返回的是大于ans的第一个数

情况二

代码分析
int bsearch_2(int l,int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid; //如果mid满足性质缩小区间为[mid,r]
        else r = mid - 1; //mid不满足性质缩小区间为[l,mid-1]
    }
    return l;
}

如果[l,r]中没有ans那么返回的是小于ans的第一个数

2.浮点数二分

例：输出x的平方根，x可能为小数

代码分析
#include<iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = x; //左右端点
    while (r - l > 1e-8) //l与r的距离小于等于1r-8退出循环
    {
        double mid = (l + r) / 2; //注意浮点数没有位运算
        if (mid * mid >= x) r = mid; //mid在答案的左边缩小区间为[l,mid]
        else l = mid; //在答案右边缩小区间为[mid,r]
    }

    cout << l; //输出l或r都行，二者相等
    return 0;
}
知识点

精度：精度eps至少需要比保留位数多2位

二分midcodeC++

有关二分的更多相关文章

  1. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  2. day1-数组part01| 704. 二分查找、27. 移除元素 - 2

    数组理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标从0开始数组内存空间的地址是连续的c++中vector和array的区别1、vector是顺序容器，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的。2、array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。3、vector的底层是array实现的二维数组二维数组在内存的空间地址是连续的704|二分查找思路1、把整个数组一分为二；2、判断目标值在左区间还是右区间，若在左区间，则修改右区间指针的位置；若在右区间，则修改新区间的左区间位置3、重复上述过程，直到lef

  3. 数学建模十大算法04—图论算法（最短路径、最小生成树、最大流问题、二分图） - 2

    文章目录一、最短路径问题1.1两个指定顶点之间的最短路径1.1.1Dijkstra算法1.1.2Matlab函数1.2每对顶点之间的最短路径1.2.1Dijkstra算法1.2.2Floyd算法1.2.3Matlab函数二、最小生成树问题2.1Kruskal算法2.2Prim算法三、网络最大流问题3.1网络流问题基础3.2Ford-Fulkerson算法3.3Edmonds-Karp算法3.4Dinic's算法3.5最小割问题（Min-Cut）3.5.1S-TCut3.5.2★最大流-最小割定理（Max-FlowMin-CutTheorem）3.5.3**寻找最小割的方法**四、二分图一、最短

  4. 代码随想录算法训练营第一天 704 二分查找、27 移除元素 - 2

    代码随想录算法Day1|704.二分查找、27.移除元素Lasteditedtime:April5,202311:27AM数据理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组下标都是从0开始的。数组内存空间的地址是连续的数组元素不能删除，只能覆盖C++中二维数组的内存的空间地址是连续的704.二分查找二分法前提：数组为有序数组，且数组中无重复元素循环不变量：对区间的定义应该是一个不变量，在边界处理中应该遵循统一原则左闭右闭：classSolution{public:intsearch(vectorint>&nums,inttarget){intleft=0;intright=num

  5. 【查找算法】二分查找(C# + 递归、非递归和变种形式) - 2

    【查找算法】二分查找(C#+递归、非递归和变种形式)写在前面：本文主要介绍二分查找算法，通过图片解析每一次查找的情况。代码通过C#实现，分别有递归、非递归和变种三种形式。其中变种主要解决数组出现重复数据的问题。最后，我们还分析了二分查找的局限性。活动地址：CSDN21天学习挑战赛本文关键字：经典算法、查找算法、二分查找、图解、C#文章目录【查找算法】二分查找(C#+递归、非递归和变种形式)一、算法效率1.时间复杂度2.空间复杂度二、查找算法1.顺序(线性)查找2.二分查找/折半查找3.插值查找4.斐波那契查找三、算法实践1.图解算法原理2.算法实现非递归实现递归实现3.二分查找变种3.时间复杂

  6. 二分图（概念、相关算法和题目应用）(全面整理) - 2

    TP二分图的概念：二分图常用算法：染色法（判断一个图是否为二分图）：匈牙利算法（求出二分图的最大匹配数）：相应题目应用：二分图染色应用：Acwing：关押罪犯二分图最大匹配应用：Acwing：棋盘覆盖洛谷：矩阵游戏二分图最大匹配的一些推论：二分图最小点覆盖应用：Acwing：机械任务Acwing：泥地二分图最大独立集应用：Acwing：骑士放置二分图最大路径点覆盖与最大路径重复点覆盖应用：Acwing：捉迷藏二分图的概念：二分图通常针对无向图问题（有些题目虽然是有向图，但一样有二分图性质）在一张图中，如果能够把全部的点分到两个集合中，保证两个集合内部没有任何边，图中的边只存在于两个集合之间，这

  7. 新冠肺炎胸部 CT 基于3D-CNN实现二分类 - 2

    新冠肺炎胸部CT基于3D-CNN实现二分类作者:WangXi2016日期:2022.10.27摘要:本示例教程使用3DCNN实现CT数据二分类。1、介绍本示例将展示构建3D卷积神经网络（3DCNN），以预测电子计算机断层扫描（CT）是否感染新冠病毒肺炎。2DCNN通常用于处理RGB图像（3个通道）。3DCNN：它将3D数据或2D帧序列（例如CT扫描中的切片）作为输入，这个架构可以从3D深度或者连续视频帧中产生多通道的信息，然后在每一个通道都分离地进行卷积和下采样操作。最后将所有通道的信息组合起来得到最终的特征描述。2、解压数据集完整数据集链接：https://www.medrxiv.org/c

  8. java - 为什么 CompletableFuture allOf 方法会进行二分查找？ - 2

    我想知道CompletableFuture的allOf方法是否进行轮询或进入等待状态，直到所有CompletableFutures都传递给该方法完成他们的执行。我查看了IntelliJ中的allOf方法的代码，它正在执行某种二进制搜索。请帮助我找出CompletableFuture的allOf方法实际上做了什么。publicstaticCompletableFutureallOf(CompletableFuture...cfs){returnandTree(cfs,0,cfs.length-1);}/**Recursivelyconstructsatreeofcompletions.*

  9. c++ - 如何找到二分查找算法的迭代次数？ - 2

    如何获取二分查找的迭代次数？这是我的代码:intmain(){inttarget=11;intN=10;std::vectorindex;intnum;for(inti=0;i我想知道迭代次数取决于N。我知道这个算法是如何工作的，但我想要迭代次数用数学表示。 最佳答案 我会通过使用递归二进制搜索函数来递归递增。在二进制检查的每个分支中，只需递增1即可递归计算迭代次数。Seelivehere#include#includestd::size_tbinarySearch(conststd::vector&arr,//passarraya

  10. C++ 字符串数组二分查找 - 2

    stringHaystack[]={"Alabama","Alaska","AmericanSamoa","Arizona","Arkansas","California","Colorado","Connecticut","Delaware","DistrictofColumbia","Florida","Georgia","Guam","Hawaii","Idaho","Illinois","Indiana","Iowa","Kansas","Kentucky","Louisiana","Maine","Maryland","Massachusetts","Michigan","M

随机推荐