问题标题: 酷町堂：2773 二分查找3

Question

0

已解决

黄昊轩

新手守护

2773 二分查找3

题目描述 Description

从一个有序的整数序列中查找整数k，如果存在输出最后一次出现位置，否则输出-1。序列有重复元素，并且单调递增。

输入描述 Input Description

第一行两个整数空格分开，分别表示序列长度n以及查询次数m。
第二行输出n个整数
接下来m行，每行一个整数，表示查询的数字

输出描述 Output Description

输出m行，每行为查询数字的位置（位置从1开始算）。

样例输入 Sample Input

5 3
2 2 3 4 5
3
2
6

样例输出 Sample Output

3
2
-1

数据范围及提示 Data Size & Hint

1000<=n<=100000
1000<=m<=100000

求各位大佬教教我

@陆麟瑞@栾峻岩 @黄俊博 @樊澄宇 @陶旭杰

黄昊轩在2018-07-26 20:33:30追加了内容

Answer 1

已采纳

陆麟瑞

资深天翼

STL大法好

c++里有个自带二分查找的函数

while(q--)
    {
        int x;
        cin>>x;
        if(!b[x])//如果没有出现过x
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<(lower_bound(a+1,a+n+1,x)-a)+b[x]-1<<endl;//不用写二分查找函数啦qwq
    }

b数组是用来统计每个数是否出现过的。

如何定义b数组：

map<int,int>b;

map是一种特殊的数组存储方式。

头文件：用van♂能头文件

预处理：

for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        b[a[i]]++;
    }

Answer 2

王文博

缔造者之神

1

Answer 3

颜咏春

中级光能

for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    while(m--)
    {
        cin>>t;
        int l=1,r=n+1,mid;
        while(l<r)
        {
            mid=(l+r)/2;
            if(a[mid]>t)    r=mid;
            else l=mid+1;
        }
        if(a[l-1]!=t)   cout<<-1<<endl;
        else cout<<l-1<<endl;
    }

Answer 4

朱小川

缔造者

函数

Answer 5

黄俊博

资深光能

int findFirst(int a[],int n,int k)
{
   int l=1,r=n;
   while(l<r)
   {
       int mid=(l+r+1)/2;
       /*
           a/b
           (a+b)/b
       */
       if(k<=a[mid])r=mid-1;
       else l=mid;
   }
   if(a[1]==k)return 1;
   if(r<n && a[r+1]==k)return r+1;
   return -1;
}

黄俊博在2018-07-27 10:27:51追加了内容

函数部分

问题标题: 酷町堂：2773 二分查找3

5 个回答: