二分查找,样例都对,二分的细节哪里错了
  • 板块P1918 保龄球
  • 楼主fufuQAQ
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/17 19:00
  • 上次更新2023/10/28 03:26:25
查看原帖
二分查找,样例都对,二分的细节哪里错了
668320
fufuQAQ楼主2022/4/17 19:00
cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,m,ans;

struct ty
{
	int pos;//下标 
	int ans;//数量 
}a[N];

int binary_search(ty a[],int t)
{
		int l=1; int r=n-1;//n个数的意思 
		while(l<=r)
		{
			int mid=l+(r-l)/2;
			if(a[mid].ans > t)  r=mid-1;
			else if(a[mid].ans < t)  l=mid+1;
			else if(a[mid].ans ==t)  return a[mid].pos;	
        }
        
        if (l >=n || a[l].ans != t) //退出条件           
               return 0;
        return a[l].pos;
}

bool cmp(ty a,ty b)
{
	return a.ans < b.ans;
}

int main()
{
	cin>>n; 
	for(int i=1;i<=n;i++)
	{
	   cin>>a[i].ans;
	   a[i].pos=i;
    }
	sort(a+1,a+1+n,cmp);
	cin>>m;
	while(m--)
	{
        int t;
        cin>>t;
        cout<<binary_search(a,t)<<endl;
	}
	return 0;
}
2022/4/17 19:00
加载中...