https://blog.csdn.net/WJPnb1/article/details/126360962?spm=1001.2014.3001.5502
这篇blog写的好，不用考虑mid-1和mid+1的边界问题

真的不错！！

这博客里最后直接输出ll不行吗

可以的 因为最起码也有起始位置可以当成终止位置来输出

好理解且几乎不会错！！！

这个是不是只能针对数组使用，还是有局限性的？

为什么用这个思想写分巧克力问题就会出错

大佬解决了吗 我一直没想明白为啥报错

太棒啦，直接通透！

已经搞懂了，这个思想一开始将左指针赋值为-1是因为刚好在所要区间的左端（也就是说对于一个数组来说，左指针赋值为-1满足条件左右指针把需要求的整个区间包含进去了，

但是分巧克力问题很显然最小的可能是1，也就是每个巧克力可以分的最小边长肯定是1，不可能是0，所以左指针要赋为0，这样就把整个要求的答案区间包含进去了。

不得不说这个二分写法理解后确实要好记许多

真不错，感觉自己又有脑子了

确实很好，但是我更习惯y总的

牛的 这个写法确实想不到

逐渐头大

### 好难理解

看到曾经的自己

###
你可以的

加油

只要一个三分支结构的模板，大家看看

#include <iostream>
using namespace std;
const int N = 1E5+20;
int n,a[N],q,k;
int binary1(int l,int r,int x){
    while(l < r){
        int mid = l + (r - l) / 2;
        if (a[mid] > x) r = mid - 1;
        else if (a[mid] < x) l = mid + 1;
        else if (a[mid] == x){
            if (a[mid - 1] != x && mid >= 0) return mid ;
            else r = mid - 1;
        }
    }
    if (a[l] == x) return l;
    else return -1;
}
int binary2(int l,int r,int x){
    while(l < r){
        int mid = l + (r - l) / 2;
        if (a[mid] > x) r = mid - 1;
        else if (a[mid] < x) l = mid + 1;
        else if (a[mid] == x){  // 2 2 2 2 2
            if (a[mid + 1] != x && (mid + 1) <= n) return mid ;
            else l = mid + 1;
        }
    }
    if (a[l] == x) return l ;
    else return -1;
}
int main(){
    scanf("%d",&n); scanf("%d",&q);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);

    while(q--){
        scanf("%d",&k);
        cout << binary1(0,n-1,k) << ' '<< binary2(0,n-1,k) << endl;
    }
    return 0;
}

我觉得 l + r >> 1可以写成 l + (r - l) / 2
从数学角度两个式子是等量的同时也能防止右值过大而爆int使得mid溢出
同时 l + r + 1 >> 1可以写成 l + (r - l) / 2 + 1,一样的道理

没事的，之前写l+r>>1是为了节省时间，现在编译器都有自动优化，所以写不写都不所谓了

编译器可不会做这种优化，这是两种计算方式，至少到目前为止 C++ 编译器还不会智能到将一种数值计算转化为另一种算法不同的数值计算。不信你可以试试看:

    int l = INT_MAX - 2000;
    int r = INT_MAX - 1000;
    int m1 = l + r >> 1;
    int m2 = l + (r - l) / 2; 

    cout << m1 << " " << m2 << endl;

看看 m1, m2 分别是多少

这是两种运算符的本质性差异吧，/2 本来就不能和 >>1 完全等价

是的，但就这道题给出的数据范围而言是不用的，不过这个防溢出的思想是很好的！

goodgood

但l+r>>1其实和(l+r)/2时间其实都一样。我写l+r>>1是懒得写括号。

一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数。看到你这句话豁然开朗，因为需要找到这个>=x的第一个数所以有Mid = l+r>>1,因为需要找到<=x的最后一个数，所以有mid = 1+l+r>>1

希望更丰富的展现？使用 $\text{Markdown}$、$\LaTeX$。

不是数学公式LaTeX可能用不上，markdown我csdn上面的题解，后期都是使用Markdown编辑的，三年前的题解可能还没注重阅读体验

只要是数字都可以用 LaTeX 啊，比如 2 就是 $2$：$2$。

用 MarkDown 排版看着比较舒服

@树雪雪查

*方法一：
#include<iostream>

using namespace std;

const int N = 100010;

int a[N], n, q;

int main()
{
    scanf("%d%d", &n, &q);

    for(int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);
    while(q --)
    {
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;

        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if(a[l] == x) cout << l << ' ' ;
        else cout << -1 << ' ' ;

        l = 0, r = n - 1;

        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(a[mid] <= x) l = mid;
            else r = mid - 1;
        }

        if(a[l] == x) cout << l <<endl ;
        else cout << -1 << endl;

    }

    return 0;
}

*方法二：

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], n, q;

int bsearch(int a[], int x)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if(a[l] == x) return l;
    return -1;
}

int esearch(int a[], int x)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    if(a[l] == x) return l;
    return -1;
}

int main()
{
    scanf("%d%d", &n, &q);

    for(int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);

    while(q --)
    {
        int x;

        scanf("%d", &x);
        cout << bsearch(a, x) << ' ' << esearch(a, x) << endl;
    }

    return 0;
}

生活中的实例：
某拍卖行： 50 一次， 50 两次， 150 一次， 150 两次， 150 三次， 300 一次…
经理： 帮我统计下xx 这个价位有几个人， 第一次叫价什么时候，最后一个叫这个价什么时候

啊啊啊啊啊泰裤辣

写的真好

感谢，二分的边界在这看懂了。

岩岩钟山首，赫赫炎天路。昂昂累世士，结根在所固。

如果你的target比数组中所有的数都大，那么结束后l的下标应该就是a.size(), 这时候你直接判断a[mid] != x,应该会报错的啊

$$\color{darkblue}{费曼学习法}$$

为什么我写的时候样例不过，提交确能够成功

$I AK I$

为啥l=0，r=n-1和l=-1，r=n和l=1，r=n+1，都对

当查找结束时，l与r相遇，l所在元素若是x则一定是x出现最小位置，因为l左边的元素必然都小于x
这句话不懂，那他为什么没有可能是 第二个 x 呢，为什么 l 左面没有相同的 x

这是查找x的起始位置，判断条件是a[mid] < x时，l = mid + 1,否则r = mid，不难看出当l移动的时候必然是mid所在的位置即a[mid]一定是小于x的，此时l指针移动，下标加一，增加后的左指针指向的值有两种情况，要么小于x，要么等于x（因为表是有序的嘛，这也是二分的前提），小于x时，左指针l等待下一次移动；等于x时，左指针不再移动，等待右指针r逼近（因为右指针判断条件是if(a[mid] >= x) r = mid,那么a[mid]大于x时，右指针移动，当a[mid] 等于x时，右指针也移动，由于向下取整的特性，当r > l且a[l] == x时，右指针一定会向左逼近。）

为什么不能把求左边和右边的点的模板交换呢

不交换你输出的是[起始点,终止点]，交换以后输出的是[终止点,起始点]，刚好相反