为什么写的二分不对

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=2e5;
   
4. typedef long long ll;
   
5. ll a[N],b[N];
   
6. int n,m;
   
7. int  main()
   
8. {
   
9.     cin>>n>>m;
   
10.     vector<ll>c(n+m);
    
11.     for(int i=0;i<n;i++)
    
12.     {
    
13.         cin>>a[i];
    
14.         c[i]=a[i];
    
15.     }
    
16. 
    
17.     for(int j=0;j<m;j++)
    
18.     {
    
19.         cin>>b[j];
    
20.         c[n+j]=b[j];
    
21.     }
    
22.     sort(c.begin(),c.end());
    
23.     for(int i=0;i<m;i++)
    
24.     {
    
25.         ll ans=b[i],r=0,l=c.size()-1,cnt=0;
    
26.         while(l<r)
    
27.         {
    
28.             ll mid=l+(r-l)/2;
    
29.             if(c[mid]>=ans)r=mid;
    
30.             else l=mid+1;
    
31.             
    
32.         }
    
33.         cout<<l+1<<" ";
    
34. 
    
35.     }
    
36. 
    
37. }
    
38. //直接写超时，所以用二分

复制代码

isdkz

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

修改后的代码如下：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=2e5;
   
4. typedef long long ll;
   
5. ll a[N],b[N];
   
6. int n,m;
   
7. int main()
   
8. {
   
9.     cin>>n>>m;
   
10.     vector<ll>c(n+m);
    
11.     for(int i=0;i<n;i++)
    
12.     {
    
13.         cin>>a[ i];
    
14.         c[ i]=a[ i];
    
15.     }
    
16. 
    
17.     for(int j=0;j<m;j++)
    
18.     {
    
19.         cin>>b[j];
    
20.         c[n+j]=b[j];
    
21.     }
    
22.     sort(c.begin(),c.end());
    
23.     for(int i=0;i<m;i++)
    
24.     {
    
25.         ll ans=b[ i],r=0,l=c.size()-1,cnt=0;
    
26.         while(l<=r)
    
27.         {
    
28.             ll mid=l+(r-l)/2;
    
29.             if(c[mid]>=ans) r=mid-1;
    
30.             else l=mid+1;
    
31.         }
    
32.         cout<<l<<" ";
    
33. 
    
34.     }
    
35. 
    
36. }
    

复制代码

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 初始化反了

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=2e5;
   
4. typedef long long ll;
   
5. ll a[N],b[N];
   
6. int n,m;
   
7. int  main()
   
8. {
   
9.     cin>>n>>m;
   
10.     vector<ll>c(n+m);
    
11.     for(int i=0;i<n;i++)
    
12.     {
    
13.         cin>>a[i];
    
14.         c[i]=a[i];
    
15.     }
    
16. 
    
17.     for(int j=0;j<m;j++)
    
18.     {
    
19.         cin>>b[j];
    
20.         c[n+j]=b[j];
    
21.     }
    
22.     sort(c.begin(),c.end());
    
23.     for(int i=0;i<m;i++)
    
24.     {
    
25.         ll ans=b[i],l=0,r=c.size()-1,cnt=0; // 改了这里
    
26.         while(l<r)
    
27.         {
    
28.             ll mid=l+(r-l)/2;
    
29.             if(c[mid]>=ans)r=mid;
    
30.             else l=mid+1;
    
31.             
    
32.         }
    
33.         cout<<l+1<<" ";
    
34. 
    
35.     }
    
36.         return 0;
    
37. }
    
38. //直接写超时，所以用二分

复制代码