二分

二分查找与二分答案本质上都是对枚举过程的一种优化，其思想是通过对有序数据进行二分，找出答案所在的范围，从而快速缩小答案的可能范围，减少枚举所需的次数。

其核心思想是“分而治之”，它通过不断将待搜索区间折半，从而极快地缩小目标范围。

算法的过程始于确定搜索范围的左右边界。在每一步中，它取中间位置的元素与目标值进行比较。如果中间元素等于目标值，则查找成功；如果中间元素小于目标值，则说明目标只可能存在于右半区间；反之，则存在于左半区间。通过这种方式，每次比较都能排除掉一半的无效数据。

它的巨大优势在于其惊人的效率，时间复杂度为 $O(\log_{}{n})$。这使得即使面对海量数据，它也能在极少的步骤内完成查找，是优化搜索问题的首选工具。

1.二分查找

1.1二分查找模版

数组中查找 $x$、大于等于 $x$ 的第一个数、大于 $x$ 的第一个数，都属于是标准的二分查找。此类问题可以采用标准模版完成，即对当前区间的中间值进行判断，确定答案在左半区还是右半区，从而进行区间范围的调整。每种情况都只需要考虑两件事，是否符合要求以及范围如何调整。

int L=1;
int R=n;
int ans=-1; // 答案初始值表示找不到答案的结果
while(L<=R){
    int mid=(L+R)/2; // 找中间

    if(a[mid]>x){
        
    }
    else if(a[mid]==x){
        ans=mid; // 符合要求 记录答案
        break; // 调整范围或结束查找
    }
    else if(a[mid]<x){
        
    }
}

在一维数组中的查找还可以直接使用 lower_bound 和 upper_bound 函数，可以直接得到大于等于 $x$ 的第一个数和大于 $x$ 的第一个数的下标。

基于这两个查询的结果，还有一些变化的形式，比如使用 lower_bound-1 查询小于 $x$ 的最后一个数下标，使用 upper_bound-lower_bound 查询 $x$ 在数组中的出现次数。

练习题

• 查找x
• 第一个大于等于x的数
• 第一个大于x的数
• 小于n的个数
• lower and upper bound
• A-B 数对

1.2 二分查找+前缀和

二分查找除了找指定值，有时还需要找位置，这个位置可以表示分界线或范围的边界。此时可能需要计算范围内的总和，可以结合前缀和的思想优化计算的过程。即二分查找减少范围的枚举次数，前缀和优化每次枚举的计算速度。

练习题

• 驯鹿和雪橇
• [GESP202409 三级] 平衡序列

2.二分答案

2.1 二分答案模版

在数据无序，但答案存在有序规律时，我们可以对答案进行二分枚举，这就是二分答案。在思想和代码结构上与二分查找比较相似，但是二分答案时对于中间值并不能直接判断，而是需要进行一些额外的检查计算才能确定答案所在的半区。

while(L<=R){
    int mid=(L+R)/2; // 找中间
    
    if(check(mid)) // check 函数进行检查计算
    //check结果同样按三种情况分别记录答案并调整范围
}

二分答案的重点在于对当前中间值的检查计算，以及答案变化对情况的影响，这一步需要进行一些逻辑分析和推理。

练习题

• 砍树

2.2 二分答案+贪心

在二分答案的基础上，我们可以结合贪心的思想，在符合要求的答案中寻找最优的答案。此时我们的 check 函数比较偏向于检查答案是否符合要求，而非计算当前的结果。

练习题

• 数列分段
• 木材加工

2.3 二分答案+数学方法求表达式结果

在二分答案的基础上，我们可以将范围作为答案的上下界，缩小范围就可以得到一个答案的近似值，当符合精度要求时，就可以作为最终答案。

此类问题的难点主要在于数学方法的使用，通常没有直接的计算过程，需要自己总结或优化表达式，从而发现答案的单调性。平面直角坐标系和函数图像的绘图与观察会对寻找答案规律有所帮助。

练习题

• 二分求立方根
• 奇怪的次方
• Ethan王子的最大因子挑战

2.4 二分答案+前缀和/双指针

前缀和与双指针可以使用在二分答案的 $check$ 函数中，可以优化表示和计算的过程，从而更快地检查当前二分的答案是否符合要求。

练习题

• 关卡设计
• 第K小的和

2.5 二分+二分

二分套二分的的重点在于对每个二分对象的确定，例如一个二分确定范围另一个二分检查个数，从而确定范围应该如何调整。

练习题

• 最小不平衡值