620574Wyxppp @ 2024-02-02 11:06:57
#include <stdio.h>
#include <string.h>
int s( int a[],int find,int l)
{
int left=0,right=l-1,mid=left+(right-left)/2;
while(left<=right)
{
if(a[mid]>find)
right=mid-1;
else if(a[mid]<find)
left=mid+1;
else
{ while(mid-1>=0&&a[mid-1]==find)
{
mid--;
}
return mid+1;
break;
}
mid=left+(right-left)/2;
}
return -1;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int a[n],b[m];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
for(int i=0;i<m;i++)
{
int t;
t=s(a,b[i],n);
printf("%d ",t);
}
return 0;
}by __Rickysun__ @ 2024-02-02 11:22:29
@620574Wyxppp 我想了一个方法，但应该会超内存，定义一个长度1e9的数组会不会超内存啊，不然就可以直接查找了
by __Rickysun__ @ 2024-02-02 11:23:41
@620574Wyxppp 我觉得可以结构体排序后用二分，这样比较快（应该吧）
by __Rickysun__ @ 2024-02-02 11:24:39
@620574Wyxppp 用了是吧
by __Rickysun__ @ 2024-02-02 11:30:58
@620574Wyxppp 你这代码问题稍微有点大，定个全局变量不行吗
by __Rickysun__ @ 2024-02-02 11:40:45
@620574Wyxppp 我调了下你的代码，可是样例第三个-1输出不出来，你自己看看吧（你的二分结构问题比较大）
#include <bits/stdc++.h>
using namespace std;
int a[1000010], x, n, m;
int s(int find) {
int left = 0, right = n - 1;
while (left < right) {
int mid = (right - left) / 2;
if (a[mid] >= find) right = mid;
else left = mid + 1;
}
if (a[left] == find) return left + 1;
else return -1;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++) {
scanf("%d", &x);
printf("%d ", s(x));
}
return 0;
}by 620574Wyxppp @ 2024-02-03 10:03:23
@Rickysun OK我看看，谢谢大佬
by TLE_AK @ 2024-02-04 20:53:57
@620574Wyxppp 来个全是相同数的数组，单次时间复杂度会变成