整数二分思路详解

输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

分析：

用二分去查找元素要求数组拥有两段性，即数组中的元素存在分界线，给定条件可以将集合中元素分为两部分，一部分满足条件，一部分不满足条件。对本题而言，一个包含重复元素的有序序列，要求输出某元素出现的起始位置和终止位置，翻译一下就是：在数组中查找某元素，找不到就输出−1−1的第一个位置，较为简单：

int l = 0, r = n - 1;
while (l < r) {int mid = l + r >> 1;if (a[mid] < x)  l = mid + 1;else    r = mid;
}

当a[mid]<xa[mid]<x的最后一个位置，便不容易了：

int l1 = l, r1 = n;
while (l1 + 1 < r1) {int mid = l1 + r1 >> 1;if (a[mid] <= x)  l1 = mid;else    r1 = mid;
}

要查找不大于x的最后一个位置：

当a[mid]<=xa[mid]<=x是开区间。上面这种写法修改了循环条件使得二分不会死循环，修改了区间的开闭性使得不会查找错误。另一种解决办法就是：

int l = 0, r = n - 1;
while (l < r){int mid = l + r + 1 >> 1;if (a[mid] <= x) l = mid;else r = mid - 1;}

不修改循环终止条件，想办法解决死循环的问题，首先想下为什么查找不小于xx.

是否还有其他办法既不修改区间的开闭性和循环终止条件，又不用上取整呢？答案是肯定的。

int l1 = l, r1 = n - 1;
while (l1 < r1) {int mid = l1 + r1 >> 1;if (a[mid] <= x)  l1 = mid + 1;else    r1 = mid - 1;
}
printf("%d %d\n", l, l1 - (a[l1] == x ? 0 : 1));

我们之所以会进行第二轮查找不大于xx，所以加上这个判断就可以解决该问题了。这也是二分程序可能遇见的第三种问题，当左右指针都移动时，待查找元素处在元素末尾会引起查找错误。总的代码如下：

#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() {scanf("%d%d", &n, &q);for (int i = 0; i < n; i++)    scanf("%d", &a[i]);while (q--) {scanf("%d", &x);int l = 0, r = n - 1;while (l < r) {int mid = l + r >> 1;if (a[mid] < x)  l = mid + 1;else    r = mid;}if (a[l] != x) {printf("-1 -1\n");continue;}int l1 = l, r1 = n;while (l1 + 1 < r1) {int mid = l1 + r1 >> 1;if (a[mid] <= x)  l1 = mid;else    r1 = mid;}printf("%d %d\n", l, l1);}return 0;
}