FengYuXinMing @ 2023-05-27 10:32:21
//来自洛谷P2249 【深基13.例1】查找
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn],n,m;
int change(int s){//二分
int left = 1, right = n, mid;
while(left <= right){
mid = (left+right)/2;
if (a[mid] = s)
right = mid - 1;
else if (a[mid] < s)
left = mid + 1;
}
if (a[mid] == s){
return mid;
}
return -1;
}
int main() {
cin>>n>>m;
for (int i = 1; i <= n;i++) cin >> a[i];
for (int i = 1;i <= m;i++){
int q;
cin >> q;
int ans = change(q);
cout << ans << ' ';
}
return 0;
}by LiJoQiao @ 2023-05-27 10:40:51
由于二分第一次找到的数不一定是第一次出现（左边可能还有） 所以会出错
by LiJoQiao @ 2023-05-27 10:42:15
解决方法：
在change这个函数内部定义一个新变量来存储位置，如果mid>s或mid<s就缩小范围，当mid==s时更新一下这个存储位置的变量，然后向左继续搜索（右侧搜到的答案都是错的，留给lz思考）
by LiJoQiao @ 2023-05-27 10:42:45
我的代码
int check(int num)
{
int l=1,r=n,mid=(l+r)>>1,loc=-1;//区间初始为[1,n]
while(l<=r)//查找
{
mid=(l+r)>>1;//折半查找
if(a[mid]>=num)
{
if(a[mid]==num)//等于则更新位置
{
loc=mid;
}
r=mid-1;
}
else//a[mid]小于num
{
l=mid+1;
}
}
return loc;//返回位置
}by FengYuXinMing @ 2023-05-27 19:52:49
@LiJoQiao 谢谢，我回头再看一下
by FengYuXinMing @ 2023-05-28 19:34:56
@LiJoQiao dalao">>"是表示什么作用
by FengYuXinMing @ 2023-05-28 19:45:52
@LiJoQiao 我明白了，二分查找第一次查到的不一定是第一次出现的，所以暂时储存，然后再循环一遍，看看左边是不是还有，还有的话第一次就是错误的，所以要存起来，谢谢奆佬！！！
ctj
by LiJoQiao @ 2023-05-29 18:08:32
@ababbjxzt >>是位运算符，int类型的变量整体右移n位相当于整除2的n次方
by LiJoQiao @ 2023-05-29 18:08:59
@ababbjxzt 不要ctj啊喂！
by FengYuXinMing @ 2023-05-29 19:45:10
@LiJoQiao （直接copy到主页储存器里面，小本本记下来）
by FengYuXinMing @ 2023-05-29 19:45:32
@LiJoQiao 现在可以了吗？doge