无意间發现了这个网站真是如入宝山呀，在这裡也分享一点心得，希望能对大家有点帮助。

虽然这模版真的是非常好用，但是每次在决定那个 check 函数时总是让我想破头，
因为一不小心写反就找不到了，一路跌跌撞撞后稍稍有点心得，如果有错还请各位高手指正

假设有一个总区间，经由我们的 check 函数判断后，可分成两部分，
这边以o作 true，.....作 false 示意较好识别

如果我们的目标是下面这个v，那麽就必须使用模板 1

................vooooooooo

假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2

oooooooov...................

所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦

感觉同学说的很有道理~ 我的想法和同学也类似，模板1就是在满足chek()的区间内找到左边界，模板2在满足check()的区间内找到右边界。然后无论是左边界还是右边界，都应该是整个区间中某一段满足某性质（如单调不降）与另一段不满足该性质的分界点（也就是同学的v）。如有错误，请高手指正~

总结得不错hh

没有问题hh

就是像数的范围那道题啊，x的起始位置。

同学你好，今天做了35 搜索插入位置那道题，按照以上你说的思路想了一下，如果check为(nums[m]>=target),此时左侧是false，右侧是true，使用模板1完全正确；但是如果check为(nums[m]<target)呢,按照以上思路，左侧是true,右侧为false，使用模板2，但做出来不正确，本人算法小白一个，希望同学指正

同学你好，这边我可能漏讲了一个地方，那就是 v 的属性，本身也要是 true，也就是 check 为 true 的左边界或是右边界(前提是目标一定是找得到的，不然跳出回圈后，必须加上额外判断)。所以如果你的 nums[m] < target 改成 nums[m] <= target，我想得到的结果应该就是对的了，希望我有回答正确，哈

其实模板1和模板2本质上是根据代码来区分的，而不是应用场景。如果写完之后发现是l = mid，那么在计算mid时需要加上1，否则如果写完之后发现是r = mid，那么在计算mid时不能加1。

发现了，昨天一直一知半解，今天就想通啦哈哈哈谢谢灿哥！

非常感谢！

兄弟，你真的救了我一命

老大，你说的有道理，但是关键在于如何找到满足check()的区间

tql

这里写了份代码， 好像和你说的不太一样代码如下

    nums := []int{10, 9, 8, 7, 1, 0, -1, -2, -3, -4}
    left := 0
    right := len(nums) - 1
    target := 1
    for left < right {
        mid := (left + right) >> 1
        if target < nums[mid] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    fmt.Println(left)  // =====> 这里输出4

按照你的说法， 我这里是模板1，在满足check的条件下找到左边界， 当前我的check条件为小于1的数，根据数组，小于1的数为0, -1, -2, -3, -4， 其左边界应该是0, 坐标也就是5,才对。但是这里输出了4. 想了好久也没想出来问题错在哪里， 希望指正一下。

区间划分错了吧，1 < nums[mid]把区间划分成了> 1和<= 1两段，<= 1那一段的分界点是左边界，最后输出的就是这段的左边界4。改成1 <= nums[mid]，把=1的部分划分到右边界上就行了。

写完后l=mid和r=mid应该也是和题意还有check函数的定义有关吧。我发现同一题两种写法其实都可以过。还有的把check函数写在else那个判断条件的。

我感觉rd0这位用户说的蛮好的，请问您之后搞懂这个了嘛？

过去好久了 我要回忆一下这个问题

那等你想好了告诉我一声 我也懂了现在

今天抽空想了下， 是我之前check条件理解错误了。 我的代码是 target < nums[mid], 其中target = 1, 那么也就是要找x>1的数, 也就是区分成了 x <=1和x>1， 对于这个题来说, left也就是4了。 但是我当时理解错误, 我理解成要找x<1的数了, 那么按照之前的理解, 左边界也应该是7才对(而不是我之前理解的5)

我的理解是：check函数要找的那个数，都用≥或者≤就好了，就是加一个等号

tql!!!!孩子的二分有救了，基础算法看完了，才弄懂二分怎么分，哭死

告诉你们吧，这两种情况就是一个是从小到大找，一个是从大到小找。因为二分的前提是要有序嘛～嘿嘿嘿

我说为啥一个只能找第一次出现的，一个只能找最后出现的，麻了

对的

你的这句话把我的问题直接解决了！

二分的前提并不是有序

有序才可以分区

无序也可以二分，比如局部最小值问题

y总模板加强版

int bsearch(int left, int right)
{
    while (left <= right)
    {
        int mid = left + right >> 1;
        if (check(mid)) left = mid + 1;
        else right = mid - 1;
    }
    return left或right
}

无论是求左边界还是右边界都是这一套写法
区别在于
如果要求的是左边界，那么就返回left
如果要求的是右边界，那么就返回right

可是这里的check(mid）该怎么写呢？

看题目要求，比如在非递减序数组中求左边界，判断条件就是>=，如果求右边界就是<=
就像y总强调的，函数模板是根据check(mid)这个函数决定的。我这个模板只是统一了写法，至于check(mid)函数还是要根据题意

在非递减序数组中求左边界，判断条件如果是a[mid]>=x，执行这个代码a[mid]=x的情况好像被忽略了

当a[mid]=左边界时，right会移动到mid-1的位置，之后left将一直向右移，直到超过right，跳出循环后，left就恰好指向了左边界

应该求左边界：< return l
求由边界：<= return r

注意返回前判断left或right哦!!!

//注意:数组中压根没有target,则l或r可能压根不会动,或者移动了也没找到
        if (r != nums.length && nums[r] == target) {
            return r;
        } else {
            return -1;
        }

这个check是不是得根据这个模板进行调整

这是闭区间的写法吗

二分板子，去找1 3 3 5中第一个3的下标，为啥就只能用第一个板子，第二个板子就找后面的3了，是不是可以理解对这个找坐标，第一个板子就是从左往右找，第二个板子从右往左找？

关于两个模板本质差别的一点拙见
https://www.acwing.com/blog/content/19616/

这里有个更实用的一个模板，而且很好懂，把l和r分别设置为最左边界减一和最右边界加一，check函数检测mid该数是否满足所需性质，满足的话l更新为mid，表示下标<=l的数都满足性质，不满足则r更新为mid。这样到最后l和r会只相差1，表示边界在l和r中间，根据实际情况取l或者r就可以了，这样就不用背两个模板
int l=-1,r=n;
while(l+1!=r){
int mid=(l+r)/2;
if(check1(mid))l=mid;
else r=mid;
}

网站终于又搜索功能了OHHHHH

模板666, 给y总比心♥

我觉得需要注意的边界就是l = mid 的时候，因为 mid 可能会等于 l ，这样就会进入死循环，所以第二个模板才会加一，防止进入死循环的，第一个模板情况里l = mid + 1 ，不可能和原来的区间一样，mid 也是不可能等于r的，所以说，只有l = mid 时可能出现区间不变死循环的情况，注意这个点即可。

NOI金牌大佬

是模板一找左模板二找右，可以这样理解吗

其实就是如果数组右半部分满足check()条件，就是模板1，不加1；如果数组左半部分满足check()条件，就是模板2，需要加1。

根据大佬的思路整理了一下模板应用在LeetCode704题目的汇总 https://leetcode.cn/problems/binary-search/solutions/2561788/er-fen-cha-zhao-bi-bei-mo-ban-fen-xi-by-p750k/

第一种找目标值在数组中最 左 边出现的位置
第二种找目标值在数组中最 右 边出现的位置

想提个问题各位大佬,就是我如何check 有时候我要让a[mid]>=x 这样就得到了r=a[mid],不需要加1,那么我首先让这个条件a[mid]>=x的意义是什么呢???;但是如果我写a[mid]<=x,那么我就得到了l=a[mid],这时候我就需要加1,那么我究竟应该怎么判断呢

right = mid - 1 => 要上取整 => 求mid的时候要+1

789这题将这两个情况都考虑到了

为什么两个模板返回的都是l，返回r不行吗

可以的，因为while循环结束的时候， l == r

check函数判断true里边是要包括待查找的边界点吗？

为什么模板1在满足 check() 时是调整右边界 $r$，而模板2是调整左边界 $l$？谢谢！

因为两个模板check()函数是不一样的

谢谢！