折半查找关键字

62 阅读 0 评论 41 点赞

我是靠谱客的博主失眠季节，最近开发中收集的这篇文章主要介绍折半查找关键字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

编写一个程序，输出一个数在长度为 nnn 的顺序表的从小到大的排名,并输出其在原顺序表中的下标 (下标从 111 开始)。

输入

第一行一个数 nnn, 表示这个顺序表的长度 (n≤2×105)(n leq 2 times 10^5)(n≤2×105)。

第二行有 nnn 个数，表示这个顺序表中的元素，保证这些元素两两不同，但是不保证递增，注意下标从 111 开始,所有数均 ≤2×109leq 2 times 10^9≤2×109。

第三行一个数 ttt，表示询问次数 (t≤50000)(t leq 50000)(t≤50000)。

第四行 ttt 个数，表示询问的这 ttt 个数。

输出

对于每个询问，如果这个数在顺序表中存在，那么输出一行两个数，表示所查询的数在这个顺序表中的排名和在在顺序表中的原下标，如果所查询的数原顺序表中不存在，这一行只需要输出一个 −1-1−1。

输入输出样例

样例输入 #1

8
1 3 5 6 7 10 9 8
4
1 4 8 10

样例输出 #1

【代码】

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct pai
{
   int num;
   int yuan;
   int xian;
}a[N];
bool cmp(struct pai b,struct pai c)
{
   return b.num<c.num;
}
int main()
{
   int n,m,s;
   cin>>n;
   int c[50010];
   for(int i=1;i<=n;i++)
   {
       cin>>a[i].num;
       a[i].yuan=i;
   }
   sort(a+1,a+n+1,cmp);
   int t;
   cin>>t;
   for(int i=1;i<=t;i++)
   {
       cin>>c[i];
   }
   for(int k=1;k<=t;k++)
   {
       int l=1,r=n,flag=0;
       while(l<=r)
       {
           int mid=l+(r-l)/2;
           if(a[mid].num==c[k])
           {
               flag=1;
               s=mid;
               break;
           }
           else if(a[mid].num>c[k])
           {
               r=mid-1;
           }
           else
           l=mid+1;
       }
       if(flag==0)
       cout<<"-1"<<endl;
       else
       {
           cout<<s<<" "<<a[s].yuan<<endl;

       }
   }
   return 0;
}