二分查找与基础模拟课堂笔记

一、今天的知识框架

基础模拟：按照题目顺序一步一步做
枚举：# 二分查找课堂笔记

## 一、什么是二分查找

二分查找用于在**有序数组**中快速查找一个数或一个位置。

每次取当前范围的中间位置`mid`，根据`a[mid]`判断答案在左半边还是右半边。

```text
l                 mid                 r
↓                  ↓                  ↓
1  3  3  5  7  7  7  9  12  15  18  20

普通遍历最多查找n次，二分查找只需要大约log n次。

使用条件

1. 数组必须有序。
2. 能根据中间位置判断向左找还是向右找。

---

二、二分查找基本框架

int l=1,r=n,ans=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(满足条件){
		ans=mid;
		//继续向左或向右找
	}else{
		//答案在另外一边
	}
}

三个重要位置

int l=1;             //左边界
int r=n;             //右边界
int mid=(l+r)/2;     //中间位置

移动方法

l=mid+1;             //去右半边找
r=mid-1;             //去左半边找

必须使用mid+1或mid-1排除已经判断过的mid，否则可能死循环。

---

三、七种常见二分查找

假设数组a[1]~a[n]已经按照从小到大排列。

类型1：判断x是否出现过

int l=1,r=n;
bool flag=false;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]==x){
		flag=true;
		break;
	}else if(a[mid]<x){
		l=mid+1;
	}else{
		r=mid-1;
	}
}
if(flag) cout<<"YES";
else cout<<"NO";

判断方向：

a[mid] < x：x只能在右边
a[mid] > x：x只能在左边
a[mid] = x：找到答案

---

类型2：查找x第一次出现的位置

找到x以后不能立刻结束，因为左边可能还有x。

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

核心：

找到x后记录位置，再向左找。

---

类型3：查找x最后一次出现的位置

找到x以后继续向右找。

int l=1,r=n,ans=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]<=x){
		if(a[mid]==x) ans=mid;
		l=mid+1;
	}else{
		r=mid-1;
	}
}
cout<<ans;

核心：

找到x后记录位置，再向右找。

---

类型4：查找第一个大于x的位置

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

满足a[mid]>x后，记录答案并继续向左找更靠前的位置。

---

类型5：查找第一个大于等于x的位置

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

---

类型6：查找最后一个小于x的位置

int l=1,r=n,ans=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]<x){
		ans=mid;
		l=mid+1;
	}else{
		r=mid-1;
	}
}
cout<<ans;

满足a[mid]<x后，记录答案并继续向右找更靠后的位置。

---

类型7：查找最后一个小于等于x的位置

int l=1,r=n,ans=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]<=x){
		ans=mid;
		l=mid+1;
	}else{
		r=mid-1;
	}
}
cout<<ans;

---

四、四个边界模板对比

要找的位置	满足条件	满足后移动
第一个大于x	a[mid]>x	r=mid-1
第一个大于等于x	a[mid]>=x
最后一个小于x	a[mid]<x	l=mid+1
最后一个小于等于x	a[mid]<=x

最重要的记忆方法

找第一个：满足条件后向左找。
找最后一个：满足条件后向右找。

向左找：r=mid-1
向右找：l=mid+1

---

五、二分查找综合应用：统计数量

1. 统计小于x的数有多少个

找到“最后一个小于x的位置”。

数组下标从1开始，所以这个位置就是数量。

int pos=最后一个小于x的位置;
int cnt;
if(pos==-1) cnt=0;
else cnt=pos;

2. 统计小于等于x的数有多少个

找到“最后一个小于等于x的位置”。

int pos=最后一个小于等于x的位置;
int cnt;
if(pos==-1) cnt=0;
else cnt=pos;

3. 统计大于x的数有多少个

找到“第一个大于x的位置”pos。

int cnt;
if(pos==-1) cnt=0;
else cnt=n-pos+1;

4. 统计区间[L,R]内有多少个数

找到：

left：第一个大于等于L的位置
right：最后一个小于等于R的位置

答案：

int cnt;
if(left==-1||right==-1||left>right) cnt=0;
else cnt=right-left+1;

---

六、完整查询模板

下面以“查询第一个大于等于x的位置”为例：

#include<bits/stdc++.h>
const int N =2e5+10;
using namespace std;
int n,q,a[N];
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(q--){
		int x;
		cin>>x;
		int l=1,r=n,ans=-1;
		while(l<=r){
			int mid=(l+r)/2;
			if(a[mid]>=x) ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

---

七、常见错误

1. 数组没有排序

二分查找只能直接用于有序数组。

sort(a+1,a+n+1);

如果题目已经说明数组有序，就不用再次排序。

2. 找第一个，满足后却向右找

找第一个 → 满足后向左找
找最后一个 → 满足后向右找

3. 混淆大于和大于等于

大于：>
大于等于：>=
小于：<
小于等于：<=

题目中的每个字都要对应到代码中。

4. 找不到时没有处理

int ans=-1;

只有找到满足条件的位置时才修改ans。

5. mid没有被排除

错误：

l=mid;
r=mid;

正确：

l=mid+1;
r=mid-1;

6. 查询等于x时没有检查

“第一个大于等于x”不一定等于x。

if(ans!=-1&&a[ans]==x) //x存在

7. 区间数量漏加1

从left到right一共有：

right-left+1

---

八、复习速记

二分前提：数组有序
循环条件：l<=r
中间位置：mid=(l+r)/2
向右移动：l=mid+1
向左移动：r=mid-1
无解初值：ans=-1

第一个 >x   ：满足后向左
第一个 >=x  ：满足后向左
最后一个 <x ：满足后向右
最后一个 <=x：满足后向右

第一次出现x：找到后向左
最后一次出现x：找到后向右
区间数量：right-left+1

字符串：字符编号、取模、逐个修改 二分查找：在有序数组中快速找位置 二分答案：二分一个答案，并判断是否可行

---

## 二、基础模拟

模拟题没有固定算法，关键是把题目过程翻译成代码。

### 做题步骤

1. 先找输入、输出和结束条件。
2. 用变量表示题目中的状态。
3. 按题目给出的先后顺序执行。
4. 用样例和极端情况检查结果。

### 常见模拟模型

#### 1. 遇到特殊值停止

```cpp
while(cin>>x&&x!=0){
	//处理x
}

2. 倒序输出

for(int i=n;i>=1;i--) cout<<a[i]<<" ";

3. 时间换算

先全部换成分钟：

int t=h*60+minute;

算完后再换回：

int h=t/60,minute=t%60;

如果时间到了前一天：

if(t<0) t+=24*60;

4. 输出格式

两位数字需要补前导0：

if(x<10) cout<<0;
cout<<x;

---

三、枚举

枚举就是把所有可能答案逐个检查。

基本模板

for(int i=1;i<=n;i++){
	if(满足条件) //记录答案
}

多重枚举

for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		//检查(i,j)是否满足条件
	}

比例判断不要用小数

错误：

if(x*1.0/y==a*1.0/b)

正确：

if(x*b==y*a)

使用乘法可以避免浮点数误差。

---

四、字符串和字符编号

每个字符都有对应的编号：

int x=s[i]-'a';

小写字母编号范围是0~25。

凯撒密码模板

#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;
	string s;
	cin>>k>>s;
	for(int i=0;i<s.size();i++){
		int x=s[i]-'a';
		x=(x+k)%26;
		s[i]=x+'a';
	}
	cout<<s;
	return 0;
}

注意

• 超过z要从a重新开始。
• 循环移动通常使用%26。
• 如果字符串中有空格，使用getline，并注意清除上一行的回车。

---

五、二分查找

使用条件

1. 数组已经有序。
2. 能够判断答案在左边还是右边。

每次排除一半范围，复杂度是：

O(log n)

基本过程

int l=1,r=n;
while(l<=r){
	int mid=(l+r)/2;
	if(条件成立) r=mid-1;
	else l=mid+1;
}

---

六、二分查找七种边界

1. 查找x是否出现

先找第一个大于等于x的位置，再判断是否等于x。

int l=1,r=n,pos=-1;
while(l<=r){
	int mid=(l+r)/2;
	if(a[mid]>=x) pos=mid,r=mid-1;
	else l=mid+1;
}
if(pos!=-1&&a[pos]==x) cout<<"YES";
else cout<<"NO";

2. 第一个等于x

找第一个大于等于x，最后检查a[pos]==x

3. 最后一个等于x

找最后一个小于等于x，最后检查a[pos]==x

4. 第一个大于x

if(a[mid]>x) pos=mid,r=mid-1;
else l=mid+1;

5. 第一个大于等于x

if(a[mid]>=x) pos=mid,r=mid-1;
else l=mid+1;

6. 最后一个小于x

if(a[mid]<x) pos=mid,l=mid+1;
else r=mid-1;

7. 最后一个小于等于x

if(a[mid]<=x) pos=mid,l=mid+1;
else r=mid-1;

记忆方法

找第一个：满足后向左找，r=mid-1
找最后一个：满足后向右找，l=mid+1

---

七、二分答案

题目不是直接查数组，而是查一个答案。

判断方法

如果答案越大，越容易或越难满足条件，就可以二分。

例如“锯片还能再高吗”：

• 锯片越高，得到的木材越少。
• 高度太高可能不够木材。
• 高度越低越容易满足。

最大可行答案模板

int l=0,r=maxx,ans=0;
while(l<=r){
	int mid=(l+r)/2;
	if(check(mid)) ans=mid,l=mid+1;
	else r=mid-1;
}
cout<<ans;

计算木材量

long long sum=0;
for(int i=1;i<=n;i++)
	if(a[i]>mid) sum+=a[i]-mid;

数据较大时，区间和使用long long。

---

八、最容易出错的地方

1. 二分前忘记排序。
2. 把“第一个”写成向右移动。
3. 把<、<=、>、>=混淆。
4. 找不到答案时没有输出-1。
5. 找到边界后没有检查是否真的等于x。
6. 时间计算没有统一成分钟。
7. 比例判断使用小数，产生误差。
8. 输出图形时漏掉前导0、空格或换行。
9. 大数求和仍然使用int。
10. 二分答案中的check函数方向写反。

---

九、考前快速复习

有序数组查位置 → 二分查找
答案范围很大且有单调性 → 二分答案

第一个满足：满足后r=mid-1
最后一个满足：满足后l=mid+1

时间问题：先换分钟
比例问题：交叉相乘
字符串移动：编号后取模
无解问题：提前设置ans=-1