首页 > 其他分享 >二分查找模版

二分查找模版

时间:2023-10-30 11:24:27浏览次数:39  
标签:二分 int 模版 mid 查找 check

给定一个有序数组nums,求数组中第一个>=目标值target的下标位置和最后一个>=目标值target的下标位置。
这是一道基础的二分查找问题,关于二分的写法有很多种,难点在于对于二分边界的处理,代码编写的过程中很容易容易出现死循环问题,因此建议套用现成的一些二分模版,关于二分模版网上有很多种。
下面的代码模版来自yxc大佬的代码模版,原文链接:https://www.acwing.com/blog/content/277/

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

标签:二分,int,模版,mid,查找,check
From: https://www.cnblogs.com/BlueSky2021/p/17797331.html

相关文章

  • [计算机学习]Python 二分法
    二分法的思想二分查找的前提是对象是有序数据。以下内容摘自Pythontip.com网站。扫描二维码可以了解更多Python课程。 left=0right=sizeofarray#数组的大小while(left+1<right)mid=(left+right)/2#中间mid下标if(array[mi......
  • 用C语言,查找和判断年份是否为闰年
    今天我们来探讨一下用C程序代码来判断一个年份是否为闰年,或者题目给定一个年份区间,来查询里面有那些年份属于闰年:闰年的判断条件:1.能被4整除,但不能被100整除2.能被400整除运行结果如下:代码如下:#include<stdio.h>//打印1000到2000之间的闰年//闰年的判断条件:1.能被4整除,但不能被10......
  • java中native源码查找方法
    以Object的hashCode()方法为例:1.下载openjdk源码或从github中查找,这里以github中查找为例;2.GitHub中查找https://github.com/bpupadhyaya/openjdk-8/tree/master/hotspot源码;3.搜索到Object.c源码文件,并查找hashCode字眼,如下所示: 4.由上可知,hashCode方法实际是调用的jvm.c......
  • php 小程序信息推送公众号消息模版
    1.登录公众号,新建消息推送模版2.打开微信官方文档->找到模版消息接口https://developers.weixin.qq.com/doc/offiaccount/Message_Management/Template_Message_Interface.html3.代码/***User:xxg*Date:2023/10/2711:58*@Notes:数据处理*/......
  • 二分算法习题汇总
    一、复制书稿题目描述现在要把\(m\)本有顺序的书分给\(k\)个人复制(抄写),每一个人的抄写速度都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必须是连续的,比如不能把第一、第三、第四本书给同一个人抄写。现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数......
  • 如何在Git仓库中查找并恢复已删除的文件?
    内容来自DOChttps://q.houxu6.top/?s=如何在Git仓库中查找并恢复已删除的文件?假设我在一个Git仓库中。我删除了一个文件并提交了更改。我继续工作并进行一些更多的提交。然后,我发现在删除该文件后需要恢复它。我知道可以使用gitcheckout<commit>--filename.txt来检出一......
  • 根据二维表值区域,查找值所对应的左端行标题!
    1职场实例小伙伴们大家好,今天我们来继续讲解Excel在职场中的实例应用:如何根据二维表值区域,查找值所对应的左端行标题?这是公众号粉丝后台留言咨询的一个问题,这个问题具有一定的职场办公代表性,包含我们必须要掌握学习的基础函数以及数组思维,所以小编整理好了解题方案,以备大家不时之需......
  • C语言二分查找法新手
    如果有一天我们想通过输入一个数去查找这个数在数组的下标。我们应该怎么去实现呢?首先我们肯定要创建一个数组组,我们知道数组的数组是从零开始的,首先呢,我们要了解二分查找法可以在百度里面查到。二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采......
  • 学习笔记:二分图
    二分图引入二分图又被称为二部图。二分图就是可以二分答案的图。二分图是节点由两个集合组成,且两个集合内部没有边的图。换言之,存在一种方案,将节点划分成满足以上性质的两个集合。性质如果两个集合中的点分别染成黑色和白色,可以发现二分图中的每一条边都一定是连接一个黑色......
  • 数据结构与算法(LeetCode)第一节:认识复杂度,对数器,二分法与异或运算
    一、认识复杂度1.评估算法优劣的核心指标:时间复杂度:当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉,记为O(去掉系数的高阶项);​ 时间复杂度是衡量算法流程的复杂度的一种指标,该指标只与数据量有关,与过程之外的优化无关常见的时间复杂度(从好到坏)O......