整数二分法查找左右边界

布满荆棘的人生 2022-09-05 04:12 177阅读 0赞

## 整数二分法查找左右边界 ##

第一种是查找左边界（我这里指的是整体右边部分的分界点，即所求区间的左边）

int bsearch_1(int l, int r)
    { 
        //第二步：递归处理子问题，用while循环来实现
        while (l < r)
        { 
            //第一步：分解成子问题,这是二分的核心--范围减半
            int mid = l + r >> 1;
            if (check(mid)) r = mid;    //向左边找 //if判断mid是否满足性质，注意该性质会划分数组的右边部分
            else l = mid + 1;           //向右边找
        }
        //第三步：合并子问题.对二分算法来说，不需要这一步
        return l;   //l就是寻找的右分界点,如果数组中没有要找的点，l的值就是r,但这是一个错误答案
    }

第二种是查找右分界点

int bsearch_2(int l, int r)
    { 
        while (l < r)
        { 
            int mid = l + r + 1 >> 1;   // mid 向上取整
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

写代码技巧：当分界点为x，应当认为左边界和mid分别位于边界点的两侧，这样更容易记忆模板  
其实代码里的 check(mid)函数是怎样写的，影响了l,r边界点的更新  
详细见

[详细题解附带题目链接][Link 1]

下面是另一个博主较为详细的分析两个模板为什么不一样  
[二分法模板及其原理分析][Link 2]

[Link 1]: https://www.acwing.com/solution/content/16798/
[Link 2]: https://blog.csdn.net/qq_36381573/article/details/100628219?ops_request_misc=%257B%2522request%255Fid%2522%253A%252216291298451678026

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关【二分法查找】

使用二分法查找需要注意的点：使用二分法的前提：数组为有序数组，同时题目还强调数组中无重复元素。二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变

快来打我*/ 2023年10月16日 12:19/ 0 赞/ 46 阅读

相关查找算法——二分法

引言二分法，顾名思义，即一分为二的方法，通常用于判断在某个有序数列中是否存在某个数，由于其优秀的算法思想，时间复杂度一般都是 O(logN) ，通常要 O(N) 的遍历

傷城~/ 2022年11月13日 15:24/ 0 赞/ 239 阅读

相关整数二分法查找左右边界

整数二分法查找左右边界第一种是查找左边界（我这里指的是整体右边部分的分界点，即所求区间的左边） int bsearch_1(int l, int r)

布满荆棘的人生/ 2022年09月05日 04:12/ 0 赞/ 178 阅读

相关二分法查找

package com.abstractdatatype.search; /二分法查找/ public class BinarySearch {

亦凉/ 2022年08月13日 15:54/ 0 赞/ 210 阅读

相关二分法查找

public static int binarySearch(int[] a,int x,int n) { int left=0,right=n-1;

ゝ一纸荒年。/ 2022年06月07日 03:36/ 0 赞/ 204 阅读

相关折半查找（二分法）

package p2; public class HalfSearch \{ /\\ \ @param ：折半查找算法思想

灰太狼/ 2022年04月12日 08:59/ 0 赞/ 246 阅读

相关二分法查找

package com.test; import java.util.Arrays; import java.util.Random; import j

男娘i/ 2022年03月20日 11:56/ 0 赞/ 245 阅读

相关二分法查找

package day01.happensbefore; / @author ZerlindaLi create at 2019/5/27

- 日理万妓/ 2022年01月27日 16:23/ 0 赞/ 258 阅读

相关二分法查找

二分法查找当线性表中数据元素是按大小排列存放时，可以改进顺序查找算法，以得到更高效率的新算法——二分法 (折半查找)。 ![这里写图片描述][SouthEast]

电玩女神/ 2021年09月14日 15:00/ 0 赞/ 471 阅读

相关二分法查找

一参考文档 [https://zhangjia.io/959.html][https_zhangjia.io_959.html] [https://zhidao.baid

本是古典何须时尚/ 2021年07月25日 01:10/ 0 赞/ 438 阅读