算法DAY 1 二分法查找数的范围

题目

给定一个按照升序排列的长度为n的整数数组，以及q个查询。
对于每个查询，返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素，则返回-1 -1。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数(均在1 ~ 10000范围内)，表示完整数组。
接下来q行，每行包含- -个整数k,表示一-个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回-1 -1。

本题可在acwing基础算法课中找到详细的视频解析（y总），本文仅进行简单的归纳。

注意题目内容：给定了一个升序数组。

从做简单的进查询一次考虑，假设有一个数组为 1 2 2 3 3 4，我们需要查询元素3的始末位置，假设初始位置为0，那毫无疑问答案是3，4。用代码实现，就是采用二分法，无限二分查找左右边界。

实现二分法的基础：数组必须包含某种性质，可以是单调性，有单调性必定可以二分，但是无单调性未必不可二分。

简单的来说，我们先查找左边界，设左右分别为l和r(初始值l=0,r=n-1)，mid=(l+r)/2,此时需要进行判断。

1.如果q[mid]>=x(x为我们的被查询元素，下文同)，以mid为分界点，实际上初始值应该在mid左侧包括mid，此时令r=mid。

2.反之(q[mid]<x)，以mid为分界点，世界上初始值应该在mid左侧，不包括mid,故而l=mid+1。

如此循环往复，知道查找出初始值位置。

此后我们在去查找右边界值，设数组的左右边界值为l和r（同上），但此时mid=(l+r+1)/2，此处与上文不同，再进行判断。

1.如果q[mid]<=x，以mid为分界点，终末值实际上在mid右侧，包括mid，l=mid。

2.如果q[mid]>x，以mid为分界点，终末值实际上在mid左侧，r=mid-1。

此处我们可以解释为什么mid=(l+r+1)/2，实际上与后续的判断有关。如果mid=（l+r+）/2,假设(l+r)为奇数，会向下取整（假设l=3，r=4，mid=3，终末值在4，q[r]=q[l]），此时就会陷入死循环。如果答案为偶数，那说明区间内至少还有三个元素，仍会发展到奇数的环节。

至于为什么查找左边界值时不需要+1，应该是因为计算机向下取整的机制，考虑到上述的问题（假设l=3，r=4，mid=3，终末值在4，q[r]=q[l]），代码符合条件。

#include<iostream>
using namespace std;
const int N=100010;//升序排列的数组
int q[N];
int main() {
	int n,m;
	cin >>n>>m;
	for (int i = 0; i < n; i++) cin >> q[i];
	while (m--) {
		int x;
		cin >> x;
		int l = 0, r = n - 1;//区间定位
		while (l < r) {
			int mid = l + r >> 1;//若l+r为奇数，则mid向下取整
			if (q[mid] >= x) r = mid;
			else l = mid + 1;
		}
		if (q[l] != x) cout << "-1 -1" << endl;
		else {
			cout << l << " ";
			int l = 0, r = n - 1;
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (q[mid] <= x) l = mid;
				else r = mid - 1;
			}
			cout << l << endl;
		}
	}
	return 0;
}

实际上代码中有两个模板，查找左边界值和右边界值。

看到评论区有种特殊的记法，男左女右（本文可以反着记，男右女左），男1女0，故而右边界需要+1，左边界无需+1。