64分，求调

P2249 【深基13.例1】查找

Zzy20060323 @ 2024-10-04 10:04:23

#include<stdio.h>
int n, m,mid;
int a[1000005];
int b[1000005];
int ss(int x,int begin, int end)
{
    if (begin > end)
    {
        return -1;
    }
    mid = (begin + end) / 2;
    if (a[mid] < x)
    {
        return ss(x, mid + 1, end);
    }
    else if (a[mid] > x)
    {
        return ss(x, begin, mid - 1);
    }
    else
    {
        int k = mid;
        while (a[k] == a[mid])
        {
            k--;
        }
        return (k + 1);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int ans=ss(b[i], 1, n);
        printf("%d ", ans);
    }

    return 0;
}

by lacha @ 2024-10-05 20:52:06

@Zzy20060323 数据量很大，通过从前往后遍历的方式，时间复杂度太高，所以采用二分法。但是要寻找最开始出现的位置，则需要找到目标值后，通过一个变量记录目标值出现的位置，然后继续往左边找，知道循环退出。

by liujunyua @ 2024-10-14 17:07:25

可以直接使用STL中的标准二分函数（懒人专用）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+1;
int a[N];
int b[N];
int main(){
    int n;
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
      int k=1;
    while(m--){
        int q;
        scanf("%d",&q);
        if(binary_search(a+1,a+1+n,q))//判断是否出现过
            printf("%d ",lower_bound(a+1,a+1+n,q)-a);//出现过，输出第一次大于等于它的编号
        else
           printf("-1 ");
    }
    return 0;
}