(1) 左边界的意思是第一个满足条件的数

(2) 右边界的意思是最后一个满足条件的数

(3) 这两个算法大致相同，但是，有一些细微的差别。而这个细微差别又很重要，如果不注意这个问题，那会导致整条题 1 分都拿不到的。

(4) 这个陷阱只存在于查找右边界问题中。我们注意了这个问题，可以用同样的方法来解决查找左边界问题，最终两个问题用一种代码来实现

题目描述

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

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

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

输入格式

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

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

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

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

输出格式

按题意输出位置或者 -1 。

样例

6
1 2 2 2 3 3
3
3 2 5

6 4 -1

错误代码

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,x;
int main()
{
	int i,q;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	scanf("%d",&q);
	int low,mid,high; 
	while(q--)
	{
		scanf("%d",&x);	

		low = 1;
		high = n;
		while(1)
		{
			if(a[low]>x||a[high]<x||low>high)
			{
				printf("-1 "); //找不到 
				break;
			}
				

			mid=(low+high)/2;
			if(a[mid]==x)
			{
				if(low==high) //区间内只有1个数，这个数又等于x，那这个数就是我们要找的数
				{
					printf("%d ",mid);
					break;					
				}
				else //区间内不止1个数，虽然 a[mid]=x，但是有可能它并非是最后一个等于x的数，还要继续找 
					low = mid; 
			}
			else if(a[mid]<x)
				low = mid;
			else
				high = mid;	
		}
	}
	return 0;
}

上面这个代码，逻辑上没毛病的，看起来非常正确。但是，如果用题目里面的测试数据，会出现死循环。为什么？

可以更明确的告诉你，死循环是在找第一个数 3 的时候，死循环的时候，low=5,high=6,所以 mid=(5+6)/2=5 。接着，用 a[5] 和 3 比较，刚好 a[5]=3 ， 既然找的是最后一个 3 出现的地方，所以，下一轮就是从 [mid,high] 里面找了，所以，下一轮还是 [5,6] ， low 和 high 没有发生变化，所以，就一直死循环下去了。

上面的原因是复杂的，多个小问题累积在一起导致的，大家可以细细品味。这个问题在查找左边界的时候不会有的，但是建议大家把这两个问题的代码写成 1 个统一的模式，便于记忆（甚至，二分等于查找也可以用这个思路）。

这个问题只会出现在区间内只剩下 2 个数的时候，然后就没办法进一步缩小区间了。所以，其中的一个解决办法是，当区间只剩下 2 个数的时候，就跳出循环。无非是 2 个数嘛，这时候写几行代码分别检验一下就好了。

程序填空

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,x;
int main()
{
	int i,q;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	scanf("%d",&q);
	int low,mid,high; 
	while(q--)
	{
		scanf("%d",&x);	

		low = 1;
		high = n;
		while( 填空(1) &&a[low]<=x&&a[high]>=x) //low和high之间还有1个数，否则就跳出循环
		{
			mid=(low+high)/2;
			if(a[mid]==x)
				填空(2);
			else if(a[mid]<x)
				填空(3);  //请按 “非简化” 模式填写
			else
				填空(4); //请按 “非简化” 模式填写
		}
		 
		//还剩下 low 和 high 两个数，分别枚举。先判断哪个是关键
		if(a[填空(5)]==x)
			printf("%d ",填空(5) );
		else if(a[填空(6)]==x)
			printf("%d ",填空(6));
		else
			printf("-1 ");
		
	}
	return 0;
}

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

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

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

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

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

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