继续介绍一步到位的二分法模板，这个课件介绍的是左边界查找。

题目描述

请在一个有序不递减的数组中（数组中有相等的值），采用二分查找，找到值 $x$ 第 $1$ 次出现的位置，如果不存在 $x$ 请输出 -1 。

请注意：本题要求出 $q$ 个 $x$ ，每个 $x$ 在数组中第一次出现的位置。

比如有 $6$ 个数，分别是：$1\ 2\ 2\ 2\ 3\ 3$ ，那么如果要求 $3$ 个数：$3\ 2\ 5$ ，在数组中第一次出现的位置，答案是： $5\ 2\ -1$ 。

输入格式

第一行，一个整数 $n$ ，代表数组元素个数( $n \le {10}^5$ )

第二行，$n$ 个整数，用空格隔开，代表数组的 $n$ 个元素 ( $1 \le$ 数组元素的值 $\le {10}^8$ )

第三行，一个整数 $q$ ，代表有要求出 $q$ 个数首次出现的位置 ( $q \le {10}^5$ )

第四行，$q$ 个整数，用空格隔开，代表要找的数 ( $1 \le$ 要找的数 $\le {10}^8$ )

输出格式

一行，含 $q$ 个整数，按题意输出要找的每个数在数组中首次出现的位置，如果不存在这样的数，请输出 -1 。

样例

6
1 2 2 2 3 3
3
3 2 5

5 2 -1

算法要点

1. while 循环的运行条件是 low<high

2. 满足条件的情况 （ a[mid]==x ），不能马上停止搜索，因为有可能在 mid 的前面还有别的数组元素等于 x ，我们只能把答案的范围缩小成 [low,mid]

3. 如果 a[mid]<x，说明第一个满足条件的数在下半区（如果存在的话），下一轮循环的搜索范围应该是 [mid+1, high]

4. 如果 a[mid]>x，说明第一个满足条件的数在上半区（如果存在的话），下一轮循环的搜索范围应该是 [low,mid-1]

5. while 语句每一次循环，[low,high] 都得到是收缩，即便在 low+1==high 的情况下也是继续收缩的。特殊情况在 low+1==high 的时候，以 low=5,high=6为例，mid=(5+6)/2=5。假设 a[mid]==x，下一轮就是搜索 [5,5]（会跳出循环）; 假设 a[mid]<x，下一轮就是搜索 [6,6]（会跳出循环）; 假设 a[mid]>x，下一轮就是搜索 [5,4]（会跳出循环）;

6. 退出 while 循环的时候，还要用 用 a[low] 检验一下（在上面的例子中，可以看到在某些情况下，high 会跑到 low 的前面，用 a[high] 来做最后的检验不合适）。

程序填空

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,m,x;
int search(int x)
{
	if(a[1]>x||a[n]<x) return -1;

	int mid,low=1,high=n;
	while(填空(1))
	{
		mid = 填空(2);
		if(a[mid]==x)
			填空(3);
		else if(a[mid]<x) //中间位置的数比 x 小，意味着 x 只可能在后半区
			填空(4);
		else
			填空(5); //中间位置的数比 x 大，意味着 x 只可能在前半区
	}
	if(a[填空(6)]==x)
		return 填空(6);
	else
		return -1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	scanf("%d",&m);
	int x;
	while(m--){

		scanf("%d",&x);			
		printf("%d ",search(x));

	}
	


	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}