为什么写的二分不对

lsmCC

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
typedef long long ll;
ll a[N],b[N];
int n,m;
int  main()
{
    cin>>n>>m;
    vector<ll>c(n+m);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        c[i]=a[i];
    }

    for(int j=0;j<m;j++)
    {
        cin>>b[j];
        c[n+j]=b[j];
    }
    sort(c.begin(),c.end());
    for(int i=0;i<m;i++)
    {
        ll ans=b[i],r=0,l=c.size()-1,cnt=0;
        while(l<r)
        {
            ll mid=l+(r-l)/2;
            if(c[mid]>=ans)r=mid;
            else l=mid+1;
            
        }
        cout<<l+1<<" ";

    }

}
//直接写超时，所以用二分

isdkz

二分查找的循环条件应该是 l <= r，而不是 l < r。因此需要将 while 循环中的条件改为 l <= r。此外，mid 的计算应该是 l + (r - l) / 2，而不是 l + (r - l)。这样可以保证在每次循环中，mid 的计算是正确的。另外，在输出答案时，应该输出 l 而不是 l+1。

修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
typedef long long ll;
ll a[N],b[N];
int n,m;
int main()
{
    cin>>n>>m;
    vector<ll>c(n+m);
    for(int i=0;i<n;i++)
    {
        cin>>a[ i];
        c[ i]=a[ i];
    }

    for(int j=0;j<m;j++)
    {
        cin>>b[j];
        c[n+j]=b[j];
    }
    sort(c.begin(),c.end());
    for(int i=0;i<m;i++)
    {
        ll ans=b[ i],r=0,l=c.size()-1,cnt=0;
        while(l<=r)
        {
            ll mid=l+(r-l)/2;
            if(c[mid]>=ans) r=mid-1;
            else l=mid+1;
        }
        cout<<l<<" ";

    }

}

FishC_GPT

问题可能出在你对二分查找的理解上。二分查找是一种递归或迭代的算法，它可以在一个已排序的数组中查找特定的值。你的代码中似乎没有体现出使用二分查找的意图。

如果你的目标是使用二分查找求解某个问题，你需要先对输入进行排序。然后，你可以通过定义上下界来确定查找范围，并在每一步中将区间缩小一半，直到找到目标值或确定目标值不存在。

例如，如果你要在一个有序数组中查找某个值x，你可以首先设置上界为数组的末尾，下界为数组的起始位置。然后，你可以计算中间位置的索引mid，比较mid处的值与x的大小关系。如果mid处的值等于x，说明找到了目标值；如果mid处的值大于x，则将上界调整为mid-1，继续二分查找；如果mid处的值小于x，则将下界调整为mid+1，继续二分查找。重复这个过程，直到找到目标值或确定目标值不存在。

希望这能帮助你理解二分查找的思想，并解决你的问题。如果你还有其他疑问，请随时提出。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

tommyyu

FishC_GPT 发表于 2023-11-22 21:24
问题可能出在你对二分查找的理解上。二分查找是一种递归或迭代的算法，它可以在一个已排序的数组中查找特定 ...

请问以上代码有什么问题，并给出正确代码

FishC_GPT

tommyyu 发表于 2023-11-22 21:34
请问以上代码有什么问题，正确代码是什么

在给出正确代码之前，我注意到你的代码有一些问题：

1. 缺少头文件声明：你需要添加 `#include <iostream>` 和 `#include <vector>` 来包含所使用的标准库。

2. 声明类型冲突：你定义了 `typedef long long ll;`，然后又使用了 `int n, m;`，这可能会导致类型冲突。建议你只保留一个类型声明，将其应用于所有相关变量。

3. 缩进和括号不正确：你的代码缩进和括号有问题，导致代码的结构混乱。请确保每个语句的缩进正确，并使用合适的括号来定义循环和条件块的范围。

4. 缺少二分查找代码：在你的代码中，并没有包含二分查找的具体实现。所以无法判断你具体的问题在哪里。

为了帮助你解决问题，我们需要更多的信息。你可以提供一下你的具体需求和预期的结果吗？这样我就能够更好地帮助你编写正确的二分查找代码了。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

tommyyu

是不是把 l 和 r 初始化反了

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
typedef long long ll;
ll a[N],b[N];
int n,m;
int  main()
{
    cin>>n>>m;
    vector<ll>c(n+m);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        c[i]=a[i];
    }

    for(int j=0;j<m;j++)
    {
        cin>>b[j];
        c[n+j]=b[j];
    }
    sort(c.begin(),c.end());
    for(int i=0;i<m;i++)
    {
        ll ans=b[i],l=0,r=c.size()-1,cnt=0; // 改了这里
        while(l<r)
        {
            ll mid=l+(r-l)/2;
            if(c[mid]>=ans)r=mid;
            else l=mid+1;
            
        }
        cout<<l+1<<" ";

    }
        return 0;
}
//直接写超时，所以用二分