二分查找进阶版

一、题目

时间限制：500ms

空间限制：64MB

很久以前，有位同学，在学完算法课的二分后，激动的振臂高呼：“我学会二分了！”。此时，一位学长从旁边经过听到此话，决定出一道题考考他，挫挫同学的锐气，让这位学弟再去好好刷二分.

学长告诉学弟n个数据，再询问他q次，每次询问告诉学弟一个x，要求学弟在每次询问给出的x的下标。

二、解题思路

那么我们该怎么根据值找下标呢，如果能做到一对一映射，每个值对应一个下标，实际上map可以做到

这个事情，也就是所谓的哈希。但是顺序是乱序，不能进行二分查找（二分查找的前提是顺序）

当然如果不使用map，我们可以尝试把无序的序列变成有序的，这时候查找值，我们就可以采取二分查找，那下标咋办呢，把下标和值绑定在一起就行，开个结构体存下标和值，排序的时间复杂度是 nlog^n ，二分查找的时间复杂度也是 nlog^n ，时间复杂度也在允许范围之内。值得注意的是，数据范围在 long long 之内，注意别爆 int 了（三年ACM一场空，不开longlong见祖宗）

​

三、源码及注释

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>//sort函数的头文件
using namespace std;
const long long N = 1e6 + 5;//满足题目对n的要求，并且稍微开大一点（+5）
typedef long long ll;//重新定义long long类型，更加方便
ll n, q, x;
struct node
{
  ll idx, num;
}arr[N];//创建结构体存储数组中的值和下标
bool cmp(node x, node y)
{
  return x.num < y.num;
}//自定义数组元素排序方法
int main()
{
  scanf("%lld%lld", &n, &q);//当数据过多时，不采用cout/cin函数，采用scanf和printf函数
  for (int i=1;i<=n;i++)
  {
    scanf("%lld", &arr[i].num);//注意long long的打印格式
    arr[i].idx = i;
  }
  sort(arr+1, arr + n+1,cmp);
  for (int i=1;i<=q;i++)
  {
    scanf("%lld", &x);
    ll left = 1;
    ll right = n;
    ll mid = 0;
    while (right >= left)
    {
      mid = (left + right) / 2;
      if (arr[mid].num > x)
      {
        right=mid-1;//注意最基本的二分查找
      }
      else if (arr[mid].num < x)
      {
        left=mid+1;
      }
      else
      {
        break;
      }
    }
    if (left <= right)
    {
      printf("%lld\n", arr[mid].idx);
    }
  }
  
  return 0;
}