二分与前缀和

文章目录

• 二分与前缀和
• • 二分
  • • 整数二分核心思想
    • 整数二分步骤总结：
    • • 题目链接
    • 实数二分核心思想：
    • • 题目链接
    • 三分法思想：

二分

难点：二分的边界问题

整数二分核心思想

1. 确定一个区间，使得目标值一定在区间中。

2. 找一个性质满足：（对于百分之95的二分拥有这个性质）

   • 性质具有二段性。
   • 答案是二段性的分界点。

   对于整数二分

整数二分步骤总结：

1. 找一个区间[L,R]，使得答案一定在该区间中。
2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
3. 分析终点M在在该判断条件下是否成立，如果成立，考虑答案在哪个区间。
4. 如果更新方式写的是R=Mid，则不用做任何处理；如果更新方式写的是L=Mid，则需要再计算Mid时加上1。

题目链接

789. 数的范围 - AcWing题库

下面是本节课总的题单，涉及前缀和等可以先不看跳过。

实数二分核心思想：

实数二分相对于整数比较简单，因为中点是基本可以取到的，没有整数一会加1，一会减去1这么绕。

加一减一无需考虑，可以说是非常简单了（滑稽，第一遍写还是WA了）。只需注意浮点数精度丢失问题，取误差在1e-8即可。

题目链接

790. 数的三次方根 - AcWing题库

三分法思想：

用的不多，这里简单提一下。

对于下图的函数，我们为了找值可以采取对斜率二分（求导即可）。或者，采取下图的三分法，当重复多次后，l与r无线逼近即可。