当前位置：首页 > article >正文

【蓝桥】二分法

article 2025/2/23 2:01:20

1、简介

1.1 定义：

通过将问题的搜索范围一分为二，迭代地缩小搜索范围，直到找到目标或确定目标不存在

1.2 适用：

有序数据集合，且每次迭代可以将搜索范围缩小一半

1.3 本质：

枚举：利用数据结构的单调性减少不必要的枚举，极大地提高了效率，一般可以优化到 $O (l o g n)$

1.4 常见类型：

1.4.1 整数二分

1.4.2 浮点二分

1.4.3 二分答案

2、解题步骤

研究并发现数据结构的单调性。
确定最大区间[l, r]，确保分界点一定在里面。
确定check函数，一般为传入mid（区间中某个下标），返回mid所属区域或返回一个值。
计算中点mid = (l + r) / 2，用check判断该移动l或r指针（根据单调性及题目要求）。
返回l或r（根据题目要求）。

3、整数二分

3.1 简介

定义：在一个已有的有序数组上，进行二分查找，一般为找出某个值的位置，或找出分界点
数组大小：一般为1e6

3.2 模板

#include <bits/stdc++.h>
using namespace std;

int main(){
	int l = 0, r = 1e9;
	
	while(l + 1 != r){
		int mid = (l + r) / 2;
		if(a[mid] >= x) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	
	return 0;
}

3.3 例题

3.3.1 题目描述

给定一个数组，其采用如下代码定义：

int data[200];
for(i = 0 ; i < 200 ; i ++) data[i] = 4 * i + 6;

现给定某个数，请你求出它在 data 数组中的位置（下标）。

3.3.2 输入描述

输入一个待查找的整数（该整数一定在数组 data 中）。

3.3.3 输出描述

输出该整数在数组中的指标。

3.3.4 输入输出样例

输入

输出

3.3.5 核心思路

数组初始化：创建一个大小为200的数组data，并根据公式4*i + 6初始化每个元素。
二分查找：使用二分查找算法高效地在排序数组中查找第一个大于或等于给定值n的元素的位置。
边界条件处理：虽然此代码未显式处理边界情况（如n小于数组最小值或大于数组最大值），但在实际应用中可能需要考虑这些情况。

3.3.6 代码

#include <iostream> // 导入输入输出流库，用于处理输入和输出
using namespace std;

int main()
{
    int data[200];
    for(int i = 0 ; i < 200 ; i++) data[i] = 4 * i + 6;

    int n; // 定义一个整数n，用于存储用户输入的目标值
    cin >> n; // 从标准输入读取n的值

    int l = 0, r = 200; // 初始化二分查找的左右边界l和r，l为0，r为200（注意这里实际上是200而非199）
    
    // 使用二分查找算法在data数组中查找第一个大于或等于n的元素的位置
    while(l + 1 != r) { // 当l+1不等于r时继续循环，确保最终l和r相邻
        int mid = (l + r) / 2; // 计算中间位置mid
        if(data[mid] >= n) // 如果中间位置的值大于或等于n，则缩小右边界
            r = mid;
        else // 否则，缩小左边界
            l = mid;
    }
    
    cout << r << '\n'; // 输出找到的位置r

    return 0;
}

4、浮点二分

4.1 简介

4.1.1 适用：

在某个实数范围内进行查找（因为实数域本身是单调的）

4.1.2 和整数二分的主要区别：

使用的变量类型、退出的判断条件

4.2 模板

// 计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
while(r - l >= eps){
	double mid = (l + r) / 2;
	if(f(mid) >= 0) r = mid;
	else l = mid;
}
cout << r << '\n';

5、二分答案

5.1 简介

5.1.1 常见模型

二分框架（时间复杂度O(logm)） + check函数（时间复杂度O(n)）

5.1.2 用法

将答案进行二分，然后在枚举出某个可能解后判断其是否可以更优或是否合法，从而不断逼近最优解

5.1.3 题目特征

如果已知某个答案，很容易判断其是否合法或更优（某些贪心问题也可以转化成二分答案）

5.2 模板

bool check(int mid){
	bool res = true;
	return res;
}

int main(){
	int l = 0, r = 1e9;
	while(l + 1 != r){
		int mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	cout << l << '\n';
}