二分
二分特点：
- 有单调性的，一定可以用二分，但二分的本质不是单调性。
- 二分的本质是能够一分为二，能够将答案始终套在我们所给的区间上，然后慢慢收缩区间直至区间大小为 1，此时就是值就是二分的结果。
- 二分一定是有解的，这个解指的是二分的解，不是答案的解！比如二分查找。
二分模版
二分的模版，是帮助你处理边界条件的，这样你在写二分的时候就不容易死循环，或者越界。 而二分的核心思想，是得慢慢做题找感觉的，总的来说，二分的细节体现在边界判断上，二分的难点在于 check 函数！
模版如下：
js
// left 和 right 的取值是根据题意来的
// 永远记住答案是在 [left, right] 闭区间内的
// 这里以最常见的二分查找举例，因为我们的答案只可能是在下标之间，
// 所以这里的 right 是等于下标，而不是长度
let left = 0
let right = length - 1
while (left < right) {
let mid = left + right >> 1
if (check(mid)) right = mid
else left = mid + 1
}
// 最后需要注意，当 left 和 right 相等时，不会进入循环
// 所以你可能需要在这里进行进一步的判断！js
// 大部分内容和模版 1 相同
let left = 0
let right = length - 1
while (left < right) {
// 只有循环内有些不同
// 这里要 +1，因为 left = mid
let mid = left + right + 1 >> 1
if (check(mid)) left = mid
else right = mid - 1
}
// 这里也同理，你可能需要在这里进行进一步的判断！两个模版，通用部分是：
- left 和 right 指的是最终结果的闭合区间，其中的 right 是下标，还是长度，取决于最终的答案的最大可能值是下标，还是长度。
- 循环判断条件是 left < right，没有等号，这样的好处是，当出循环时，保证 left 和 right 是相同的，不需要思考选择 left 还是 right
- 循环内的条件始终只有两个（除非相等时可以直接返回），都是用一个 check 函数，这个的目的是将结果区间一分为二，我们需要确保答始终在我们的 [left, right] 区间内
- 当 check 满足时，需要移动一个指针到 mid 上。原因在于 mid 本身可能是我们所需要的答案。
- 具体是将 left 赋值为 mid，还是将 right 赋值为 mid，取决于题意。
第一个模版：
- 满足 check 条件时让 right 移动到 mid 上
- 那么此时 else 的条件很明显就是 left = mid + 1。因为 mid 所在值不满足 check 条件，所以肯定不需要等于 mid，然后是 left 肯定是向右移动，所以是 mid + 1
- 中点的计算是 left + right >> 2
第二个模版：
- 满足 check 条件时让 left 移动到 mid 上
- 那么此时 else 的条件很明显就是 right = mid - 1。因为 mid 所在值不满足 check 条件，所以肯定不需要等于 mid。然后 right 肯定是向左移动，所以是 - 1
- 注意此时求中点时要加 1，也就是 left + right + 1 >> 2
说明一下为什么当 left = mid 的时候，需要让中点 + 1。
原因是这样的：通过 left + right >> 2 所得到的 mid 是可能等于 left 的。比如当 left 和 right 之间只相差 1 时，此时的 mid 就等于 left。 由于此时 mid 已经等于 left 了，而我们的赋值又是 left = mid，那么此时我们的区间大小就无法变化，永远是 2 个元素，这就会导致死循环。 所以我们需要在计算中点 mid 时 +1，也就是向上取整。 此时 mid 就不会等于 left，而是会等于 right 了。 这样一来，就能够将区间大小缩小到 1 个元素，然后就可以退出循环了！
同理，为什么当 right = mid 的时候不需要加 1？ 原因就是不加 1 的时候，计算出来的 mid 值是等于 left 而不是 right。 这样一来，将 right 赋值为 mid 时才可以继续缩小区间大小，从而防止死循环。
那么多二分模版，为什么我选择这两个呢？
关于二分，不同处理方式，你可以整理出不同的模版。 而上面两个模版是我觉得最合适。原因如下：
- 循环判断时，不需要等号，那么出循环时，就不需要思考选取 left 还是 right，因为它们是相同的！
- 模版中的条件语句，当满足 check 的时候，都是直接将 left/right 赋值为 mid，不需要考虑 +1 还是 -1 问题
- 当确定了是 left=mid 还是 right=mid 后，另外一个 else 语句也很容易确定！
- 对于为什么要加 1 这个理由，我觉得非常容易记忆。
- 最后，这个模版是 y总 给出的，人家比我厉害，那我自然就会向他学习。
总的来说，这个模版容易记忆，而且理解起来也很方便。