为什么二分查找总是在强调区间一开一闭

lzy20091001 @ 2023-07-21 22:05:07

#include <iostream>
using namespace std;

int n, m, c;
int a[1000005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int lft = 1, rgt = n;
        cin >> c;
        while (lft <= rgt)
        {
            if (lft == rgt)
            {
                if (a[lft] == c)
                    cout << lft << " ";
                else
                    cout << -1 << " ";
                break;
            }
            int mid = (lft + rgt) / 2;
            if (c <= a[mid])
                rgt = mid;
            else
                lft = mid + 1;
        }
    }
    return 0;
}

by lzy20091001 @ 2023-07-21 22:05:49

可以直接at我

by FFTotoro @ 2023-07-21 22:11:49

@lzy20091001 个人习惯吧这个，习惯怎么用就怎么用。当然正确性第一。

by Iniaugoty @ 2023-07-21 22:13:48

@lzy20091001 你这

while(l<=r){
    if(l==r){
        //do sth.
        break;
    }
    //do sth.
}

和

while(l<r){
    //do sth.
}
//do sth.

有什么区别吗？

你这个就是把正常二分写在外面的放进循环并且改了一下循环条件吧……

by uid_310801 @ 2023-07-21 22:20:55

建议写：

int l=***,r=***,ans=0;
while(l<=r){
    int mid=(l+r)/2;
    if(check(mid)){
        ans=mid;
        l=mid+1;
    }
    else{
        r=mid-1;
    }
}
cout<<ans;

这是万能的

by lzy20091001 @ 2023-07-21 22:21:03

@gty314159 哦对啊，这个最终的判断可以写在外面我才发现。对不起我之前没想到。

不过我的问题是，我在教材上看到的lft初始值设为0，并且是lft在更新时lft = mid而不是lft = mid + 1。这样左开右闭看起来怪别扭的。

by uid_310801 @ 2023-07-21 22:25:15

@lzy20091001 把上面那个代码改成ans=-1

by lzy20091001 @ 2023-07-21 22:29:09

#include <iostream>
using namespace std;

int n, m, c;
int a[1000005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int lft = 1, rgt = n;
        cin >> c;
        while (lft < rgt)
        {
            int mid = (lft + rgt) / 2;
            if (c <= a[mid])
                rgt = mid;
            else
                lft = mid + 1;
        }
        if (a[lft] == c)
            cout << lft << " ";
        else
            cout << -1 << " ";
    }
    return 0;
}

by lzy20091001 @ 2023-07-21 22:29:52

@Spouter_27 感谢赐教

by UnyieldingTrilobite @ 2023-07-21 22:31:21

@lzy20091001 主要是区间开闭的写法有差别

只要你确定自己的板子是完全正确的就没有所谓，不然一定要明确这个事情否则容易瞪逻辑瞪好久