TKteacake @ 2024-05-13 13:30:34
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000010];
int le;
ll tar;
int tt;
bool check(int mid)
{
return tar <= a[mid];
}
int solve()
{
cin >> tar;
int l = 0 ,r = le - 1;
int mid;
while (l <= r)
{
mid = (l + r) >> 1;
//cout << "tar = " << tar << "mid = " << mid << "\n";
// if (a[mid] == tar)
// {
// return mid;
// }
if (check(mid))
{
r = mid - 1;
}
else l = mid + 1;
}
if (a[mid] != tar)
{
return -1;
}
return r + 2;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> le;
cin >> tt;
for (int i = 0; i < le; i ++)
{
cin >> a[i];
}
while (tt--)
{
cout << solve() << " ";
}
}
by dongzhen @ 2024-05-13 13:56:59
你这二分有时候返回值错误
hack:
3 1
1 2 3
2
改了一下二分,注意小于和等于分开判断
int solve(){
cin >> tar;
int l = -1 ,r = le;
int mid,ans=INT_MAX;
while (l<r-1){
mid = (l+r)>>1;
if (tar<a[mid]){r=mid;}
else if(tar==a[mid]){ans=min(ans,mid);r=mid;}
else l=mid;
}if(ans==INT_MAX){ans=-2;}
return ans+1;
}
by chenxinye @ 2024-05-13 13:59:03
有必要这么做吗?