题单：二分查找（最小下标）

题目描述

给定一个包含 nn 个整数的非降序数列，以及 TT 次查询，对于每一个查询 xx，请回答 xx 在数列中的位置（从左向右，第一个位置记为 11）。

注意：

1. 若 xx 不在数列中，回答 −1 。

2. 若数列中有多个 xx ，回答最小的下标。

输入格式

第一行一个整数 nn，表示数列中整数的个数；

第二行 nn 个整数，表示数列中的元素；

第三行一个整数 TT，表示询问的次数；

接下来 TT 行，每行一个整数 xx，表示查询的整数。

输出格式

一行，TT 个整数，表示对于相应查询的回答。

样例 #1

样例输入 #1

7
1 2 3 3 5 5 6
3
4
5
6

样例输出 #1

-1 5 7

提示

对于 100% 的数据：1≤n,T≤105 。

#include<bits/stdc++.h>
using namespace std;
int a[50000005];
int bin(int l,int r,int key)
{int ans=-1;while(l<=r){int mid=(l+r)/2;if(a[mid]>key){r=mid-1;}else if(a[mid]<key){l=mid+1;}else if(a[mid]==key){ans=mid;r=mid-1;}}return ans;
} 
int main(){int n;scanf("%d",&n);int x;for(int i=1;i<=n;i++){scanf("%d",&a[i]);} sort(a+1,a+n+1);int t;scanf("%d",&t);while(t--){scanf("%d",&x);printf("%d ",bin(1,n,x));}return 0;
}