为什么写的二分不对
#include <bits/stdc++.h>using namespace std;
const int N=2e5;
typedef long long ll;
ll a,b;
int n,m;
intmain()
{
cin>>n>>m;
vector<ll>c(n+m);
for(int i=0;i<n;i++)
{
cin>>a;
c=a;
}
for(int j=0;j<m;j++)
{
cin>>b;
c=b;
}
sort(c.begin(),c.end());
for(int i=0;i<m;i++)
{
ll ans=b,r=0,l=c.size()-1,cnt=0;
while(l<r)
{
ll mid=l+(r-l)/2;
if(c>=ans)r=mid;
else l=mid+1;
}
cout<<l+1<<" ";
}
}
//直接写超时，所以用二分 二分查找的循环条件应该是 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,b;
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;
c=b;
}
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>=ans) r=mid-1;
else l=mid+1;
}
cout<<l<<" ";
}
}
问题可能出在你对二分查找的理解上。二分查找是一种递归或迭代的算法，它可以在一个已排序的数组中查找特定的值。你的代码中似乎没有体现出使用二分查找的意图。
如果你的目标是使用二分查找求解某个问题，你需要先对输入进行排序。然后，你可以通过定义上下界来确定查找范围，并在每一步中将区间缩小一半，直到找到目标值或确定目标值不存在。
例如，如果你要在一个有序数组中查找某个值x，你可以首先设置上界为数组的末尾，下界为数组的起始位置。然后，你可以计算中间位置的索引mid，比较mid处的值与x的大小关系。如果mid处的值等于x，说明找到了目标值；如果mid处的值大于x，则将上界调整为mid-1，继续二分查找；如果mid处的值小于x，则将下界调整为mid+1，继续二分查找。重复这个过程，直到找到目标值或确定目标值不存在。
希望这能帮助你理解二分查找的思想，并解决你的问题。如果你还有其他疑问，请随时提出。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。 FishC_GPT 发表于 2023-11-22 21:24
问题可能出在你对二分查找的理解上。二分查找是一种递归或迭代的算法，它可以在一个已排序的数组中查找特定 ...
请问以上代码有什么问题，并给出正确代码 tommyyu 发表于 2023-11-22 21:34
请问以上代码有什么问题，正确代码是什么
在给出正确代码之前，我注意到你的代码有一些问题：
1. 缺少头文件声明：你需要添加 `#include <iostream>` 和 `#include <vector>` 来包含所使用的标准库。
2. 声明类型冲突：你定义了 `typedef long long ll;`，然后又使用了 `int n, m;`，这可能会导致类型冲突。建议你只保留一个类型声明，将其应用于所有相关变量。
3. 缩进和括号不正确：你的代码缩进和括号有问题，导致代码的结构混乱。请确保每个语句的缩进正确，并使用合适的括号来定义循环和条件块的范围。
4. 缺少二分查找代码：在你的代码中，并没有包含二分查找的具体实现。所以无法判断你具体的问题在哪里。
为了帮助你解决问题，我们需要更多的信息。你可以提供一下你的具体需求和预期的结果吗？这样我就能够更好地帮助你编写正确的二分查找代码了。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。 是不是把 l 和 r 初始化反了#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
typedef long long ll;
ll a,b;
int n,m;
intmain()
{
cin>>n>>m;
vector<ll>c(n+m);
for(int i=0;i<n;i++)
{
cin>>a;
c=a;
}
for(int j=0;j<m;j++)
{
cin>>b;
c=b;
}
sort(c.begin(),c.end());
for(int i=0;i<m;i++)
{
ll ans=b,l=0,r=c.size()-1,cnt=0; // 改了这里
while(l<r)
{
ll mid=l+(r-l)/2;
if(c>=ans)r=mid;
else l=mid+1;
}
cout<<l+1<<" ";
}
return 0;
}
//直接写超时，所以用二分
页:
[1]