二分法是一种高效的查找方法，核心思想是通过将问题的搜索范围一分为二，每次迭代缩小搜索范围，直到找到目标或确定目标不存在。

1. 二分法的基本原理
- 核心思想：每次将搜索范围对折，利用数据的有序性（单调性）快速定位目标。
- 适用场景：
  - 数据集合是有序的（通常为单调递增或单调递减）。
  - 搜索分析中需要快速缩小范围，比如查找满足某个条件的极值。
- 效率提升：时间复杂度从暴力枚举的(O(n))优化到(O(log n))，效率极大提升。

2. 二分法的基本实现步骤

1. 初始化边界：
   • 设置左右指针left和right，分别表示搜索区间的起始和结束位置。
2. 循环条件：
   • 只要left不超过right就持续搜索。
3. 计算中点：
   • 使用公式(mid = left + (right - left) / 2)防止整数溢出。
4. 比较与调整：
   • 若mid处的值大于目标，则目标在左侧，更新right = mid - 1。
   • 若mid处的值小于目标，则目标在右侧，更新left = mid + 1。
   • 若找到目标值，立即返回。
5. 终止处理：
   • 循环结束后仍未找到则返回失败标识。

自己写的代码：

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

int main()
{
    int data[200];
for(int i = 0 ; i < 200 ; i ++)data[i] = 4 * i + 6;
int t;
scanf("%d",&t);

int l=0,r=199;//初始化左右边界
while(l<=r){
	int mid = (l+r)/2;
	if(data[mid]>t){
		r=mid;
	}
	else if(data[mid]<t){
		l=mid;
	};
	if(data[mid]==t){
		cout << mid<<endl;
		break;
	}
} 
    return 0;
}

优化之后

#include <iostream>
using namespace std;

int main() {
    int data[200];
    // 初始化有序数组（严格递增）
    for (int i = 0; i < 200; ++i) {
        data[i] = 4 * i + 6;
    }
    
    int t;
    cin >> t;  // 统一使用C++风格输入
    
    int l = 0, r = 199;
    bool found = false;  // 标记是否找到目标
    
    while (l <= r) {
        // 计算中间索引（避免l + r溢出，更安全）
        int mid = l + (r - l) / 2;
        
        if (data[mid] == t) {
            cout << mid << endl;
            found = true;
            break;
        } else if (data[mid] < t) {
            // 目标在右侧，左边界右移（跳过当前mid）
            l = mid + 1;
        } else {
            // 目标在左侧，右边界左移（跳过当前mid）
            r = mid - 1;
        }
    }
    
    // 处理目标不存在的情况
    if (!found) {
        cout << -1 << endl;  // 用-1表示未找到
    }
    
    return 0;
}

• 当 l <= r 时循环继续；一旦 l > r，表示搜索范围为空，循环终止。

  计算中间索引时采用 mid = l + (r - l) / 2 而非 (l + r) / 2，原因在于：当 l 和 r 均为较大整数时，前者能有效避免 l + r 可能导致的整数溢出问题。这两种计算方式在数学上等价，但前者更为安全可靠。

  原代码中边界更新是l = mid或r = mid，这会导致范围无法收缩（例如当l = r - 1时，mid始终等于l，循环永远无法结束）。优化后用l = mid + 1和r = mid - 1，确保每次循环范围都会缩小，避免死循环。

一、浮点二分简介

• 定义：
  浮点二分（也称实数二分）不是在有序数组上进行查找，而是在某个实数范围内寻找满足特定条件的值（如函数的零点、极值等）。

• 核心思想：
  利用单调性（例如函数单调递增或递减）在连续区间内不断缩小搜索范围，逼近目标值。

• 与整数二分的区别：

  • 变量类型不同：整数二分使用整型变量，浮点二分使用浮点型（double）。
  • 退出条件不同：整数二分通常以 l < r 为循环条件，而浮点二分通过判断区间长度是否小于一个极小量 eps 来决定是否停止。

• 适用前提：

  • 函数在搜索区间内具有单调性（如单调递增或递减）。
  • 目标值是某个临界点（如零点、最大值/最小值）。

二、浮点二分模板（代码解析）

// 计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e-6;
// 注意这里的判断条件，这样可以保证l, r最终一定收敛到分界点
while(r - l >= eps) // eps是一个极小量，设置为1e-6较合适
{
    double mid = (l + r) / 2;

    // f(x)单调递增，f(mid) >= 0，说明mid偏大了，需要减小mid，就只能将r变小，即r = mid
    if(f(mid) >= 0) r = mid;
    else l = mid;
}
// 最后返回l, r差别不大
cout << r << '\n';

关键点解析：

1. 初始化：

   • l = 0, r = 1e9：设定搜索区间。
   • eps = 1e-6：精度要求，表示当区间长度小于该值时认为已收敛。

2. 循环条件：

   • while (r - l >= eps)：保证区间足够小，最终收敛到分界点。

3. mid 计算：

   • mid = (l + r) / 2：取中点。

4. 判断逻辑：

   • 假设 f(x) 单调递增，且我们找的是 f(x) = 0 的解。
   • 若 f(mid) >= 0，说明 mid 处函数值非负，解应在左侧，故 r = mid。
   • 否则 f(mid) < 0，说明 mid 太小，解在右侧，故 l = mid。

5. 输出结果：

   • 最终 l 和 r 非常接近，返回 r 或 l 均可作为近似解。

三、图示理解

• 图中显示一个实数轴，分为两个区域：
  • Area1：函数值小于 0 的区域。
  • Area2：函数值大于等于 0 的区域。
• left 和 right 是当前搜索区间的左右端点。
• 二分过程不断缩小区间，使 left 和 right 趋近于函数的零点（即 f(x)=0 的位置）。

四、注意事项

1. 精度控制：

   • eps 设置要合理，一般 1e-6 ~ 1e-8 较常见，根据题目要求调整。

2. 函数单调性：

   • 必须确保函数在搜索区间内单调，否则无法保证正确性。

3. 边界处理：

   • 使用 >= 或 <= 时要注意逻辑一致性，避免死循环或错误收敛。

4. 浮点误差：

   • 浮点运算存在精度误差，因此不能直接比较 ==，应使用 abs(a - b) < eps 判断相等。

总结：

浮点二分是一种在实数范围内利用单调性快速逼近目标值的方法，核心是通过不断缩小区间并控制精度来求解。

 一、核心本质 二分答案是**二分法**的一种应用场景，核心是将“寻找最优解”的问题，转化为“判断某个候选答案是否合法/更优”的问题，通过**二分枚举候选答案**并结合**check函数验证**，不断逼近最优解。 ### 二、适用条件 题目需满足两个关键特征： 1. **答案具有单调性**：比如“最小的最大”“最大的最小”类问题，候选答案的“合法/不合法”状态是单调的（例如，若某个值`x`合法，那么比`x`大/小的某类值也合法）。 2. **check函数易实现**：已知一个候选答案时，能快速判断它是否“合法”（是否满足题目要求）或是否“更优”。 ### 三、解题框架 通常分为两步： 1. **二分枚举候选答案**：确定答案的**上下界`left`和`right`**（例如最小可能为`0`，最大可能为某个极值），然后通过二分法不断缩小范围。 2. **实现check函数**：对于当前枚举的候选答案`mid`，编写函数判断其是否合法（或是否能更优）。 时间复杂度为 **二分框架的O(log m) + check函数的O(n)**（`m`是答案的取值范围，`n`是数据规模）。 ### 四、典型例题（帮助理解） 以“**最大化最小值**”类问题为例，比如： > 有`n`个`k物品，要分成`组，要求每组至少一个物品，求“每组物品数量的最小值”的最大可能是多少？ - **二分枚举**：答案的范围是`[1, n]`（最少1个一组，最多n个一组）。 - **check函数**：对于候选答案`mid`，判断是否能将物品分成`k`组，且每组的数量都≥`mid`（可通过贪心策略：尽可能多分组，看是否能分出≥`k`组）。 ### 五、与其他算法的关联 某些**贪心问题**可转化为二分答案问题。比如上述分组问题，若直接贪心很难直接得到“最小的最大”，但通过二分答案+check函数就能高效解决。 总结来说，二分答案的关键是**利用单调性缩小范围**，把“找最优”转化为“验证合法性”，从而将复杂的优化问题拆解为更易处理的二分和check步骤，是算法竞赛和编程中解决“最优解”问题的常用技巧。