一、算法模板
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间\([l, r]\)中， 每次将区间长度缩小一半，当\(l = r\)时，我们就找到了目标值。
1、向左逼近
当我们将区间\([l, r]\)划分成\([l, mid]\)和\([mid + 1, r]\)时，其更新操作是\(r = mid\)或者\(l = mid + 1\)，计算\(mid\)时不需要加\(1\)。
int bsearch_1(int l, int r){
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
2、向右逼近
当我们将区间\([l, r]\)划分成\([l, mid - 1]\)和\([mid, r]\)时，其更新操作是\(r = mid - 1\)或者\(l = mid\)，此时为了防止死循环，计算\(mid\)时需要加1。
int bsearch_2(int l, int r){
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
总结：
\(mid\)划到左侧，则\(mid=(l+r)>>1\)
\(mid\)划到右侧，则\(mid=(l+r+1)>>1\)
栗子1：
\(\{2,3,4,4,4,5,6,7\}\)中找到左侧数第一个\(4\)。
-
第一步：先把\(mid=(l+r)>>1\)写上。
-
第二步: 思考\(check(mid)\)函数，写为
if(q[mid]>=x) return true;。因为只有大于等于,才能向左逼近。 -
第三步：大于等于目标值，\(mid\)是可能的解，所以\(r=mid\),如果不是，表示小于目标值，需要向右找：\(l=mid+1\)。
-
第四步：向左逼近，第一步的\(mid\)值是不需要改的。
栗子2：
\(\{2,3,4,4,4,5,6,7\}\)中找到右侧数第一个\(4\)。
-
第一步：先把\(mid=(l+r)>>1\)写上。
-
第二步: 思考\(check(mid)\)函数，写为
if(q[mid]<=x) return true;。因为只有小于等于,才能向右逼近。 -
第三步：小于等于目标值，\(mid\)是可能的解，所以\(l=mid\),如果不是，表示大于目标值，需要向右找：\(r=mid-1\)。
-
第四步：向右逼近，第一步的\(mid\)值需要\(+1\)。
二、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int q[N];//数组本身是有序的
int l, r;
int main() {
//读入优化
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> q[i];
//m次询问
while (m--) {
int x;
cin >> x;
//本题要求数组下标从0开始
l = 0, r = n - 1;
//寻找左边界
while (l < r) {
int mid = (l + r) >> 1;
if (q[mid] >= x) r = mid;//如果q[mid]>=x,那么首次出现的x应该在左侧，同时，mid位置可能是解
else l = mid + 1;//如果q[mid]<x,那么解一定在右侧，并且mid肯定不是解。
}
//如果没有找到的话
if (q[l] != x) {
cout << "-1 -1" << endl;
continue;
}
//输出左边界
cout << l << ' ';
//寻找右边界
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;
}
三、总结思考
为什么找左边界是q[mid]>=x,而找右边界是q[mid]<=x呢？
为了找最左边界，需要判断条件是大于等于，这样，中位值大于等于目标值，才会继续向左逼近。
为了找最右边界，需要判断条件是小于等于，这样，中位值小于等于目标值，才会继续向右逼近。
四、示例
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 110;
int l, r;
int main() {
//从0~5找出>=3的第一个位置
int q1[N] = {0, 1, 2, 4, 5, 7};
l = 0, r = 5;
int x = 3;
while (l < r) {
int mid = (l + r) >> 1;
if (q1[mid] >= x)
r = mid;
else
l = mid + 1;
}
cout << l << endl;
//从0~6找出<=3的最后一个位置
int q2[N] = {1, 2, 3, 3, 3, 4, 5};
l = 0, r = 6;
x = 3;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q2[mid] <= x)
l = mid;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}