**二分的本质**：
如果我们能够通过某种方式将一个区间划分成两个区间，左边区间满足某种特性；右边区间不满足某种特性。
那么我们就能够通过二分法来寻找左区间的右边端点或者右区间的左边端点

**有单调性一定可以二分，但是二分不一定要有单调性**

> 注意：**配套讲解视频：B 站《百学原理》 - 二分法专题**
> 注意：**配套分析总结文章：[二分法专题(一)](https://leetcode.cn/circle/article/hm7vFa/) [二分法专题(二)](https://leetcode.cn/circle/article/lHfPey/)**
> 注意： **部分可能涉及到知识产权的题目链接已在 LeetCode 删除，完全版在[github algos courseware](https://github.com/BruceYuj/algorithm-series-courseware)**

### 整数二分
### 代码模板
```python
binary_search(l , r): # 模板一：寻找右区间的左端点

    while l < r:
        mid = (l+r)//2

        if check(mid): r = mid
        else: l = mid+1
```

```python
binary_search(l , r): # 模板二：寻找左区间的右端点

    while l < r:
        mid = (l+r+1)//2

        if check(mid): l = mid
        else: r = mid-1
```
**为什么是整数的时候会有很多边界问题呢？**
因为整数范围缩小到 2 时候，可能进入死循环。

## 浮点数二分

```python
binary_search(l , r): # 寻找结果

    eps = 1e-6
    while r - l >= eps:
        mid = (l+r) / 2

        if check(mid): r = mid
        else: l = mid
```

## 题目汇总
### 类型一：基本二分法题目 （共 11 道）
1. [leetcode: 34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)
2. [leetcode: 74. 搜索二维矩阵](https://leetcode.cn/problems/search-a-2d-matrix/)
3. [leetcode: 153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array)
4. [leetcode: 81. 搜索旋转排序数组 II](https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/)
5. [leetcode: 154. 寻找旋转排序数组中的最小值 II](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/)
6. [leetcode: 162. 寻找峰值](https://leetcode.cn/problems/find-peak-element/)
7. [leetcode: 275. H 指数 II](https://leetcode.cn/problems/h-index-ii/)
8. [codeforces edu 4 道题目](https://codeforces.com/edu/course/2/lesson/6/1/practice)

#### 浮点数二分例题
1. [x 的平方根](https://leetcode.cn/problems/sqrtx/) 如果题目要求的是浮点数根的话，就可以用浮点数模板了。

> 其他例题已删

### 类型一： 对结果进行二分（共 18道）
1. [leetcode: 1011. 在 D 天内送达包裹的能力](https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/)
2. [leetcode: 1482. 制作 m 束花所需的最少天数](https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/)
3. [leetcode: 778. 水位上升的泳池中游泳](https://leetcode.cn/problems/swim-in-rising-water/)   
4. [leetcode: 1482. 制作 m 束花所需的最少天数](https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/)
5. [leetcode: 1292. 元素和小于等于阈值的正方形的最大边长](https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/)
6. [leetcode: 875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/)
7. [leetcode: 287. 寻找重复数](https://leetcode.cn/problems/find-the-duplicate-number/)
8. [(第八届蓝桥杯): leetcode-1231. 分巧克力](https://leetcode.cn/problems/divide-chocolate/)
9. [codeforces edu 8 道题目](https://codeforces.com/edu/course/2/lesson/6/2/practice)   
10. [leetcode: 793. 阶乘函数后K个零](https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/)
11. [leetcode: 719. 找出第 k 小的距离对](https://leetcode.cn/problems/find-k-th-smallest-pair-distance/)

### 类型三 - min(max()) / max(min()) （共 6 道）
1. [leetcode: 410. 分割数组的最大值](https://leetcode.cn/problems/split-array-largest-sum/)
3. [leetcode plus: 774. minimize-max-distance-to-gas-station](https://leetcode.cn/problems/minimize-max-distance-to-gas-station/)
5. [codeforces 4 道经典题目](https://codeforces.com/edu/course/2/lesson/6/3/practice)

### 类型四 - 求最大平均值 / 最小平均值 (共 5 道)
1. [leetcode: 644. 最大平均子段和II](https://leetcode.cn/problems/maximum-average-subarray-ii/)
2. [luogu: 1404. 求平均值(poj2018)](https://www.luogu.com.cn/problem/P1404)
3. [codeforces 3 道经典题目](https://codeforces.com/edu/course/2/lesson/6/4/practice)


### 类型五 - 求某种特殊的第 k 大 / 小 （共 6 道）
1. [leetcode: 668. 乘法表中第k小的数](https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/)
2. [leetcode: 878. 第 N 个神奇数字](https://leetcode.cn/problems/nth-magical-number/)
3. [leetcode: 786. 第 K 个最小的素数分数](https://leetcode.cn/problems/k-th-smallest-prime-fraction/)
4. [codeforces 3 道经典题目](https://codeforces.com/edu/course/2/lesson/6/5/practice)

## 其他涉及题目
在算法题目中结合多种技巧解决一道题目是很常见的事，下面就给大家列举一些**二分法**结合其他算法的题目，这些题目就不讲解了，有问题可以在答疑群里面提出来。

**数学+二分**：
1. [leetcode: 483. 最小好进制（google kickstart 2016 round E problem B）](https://leetcode.cn/problems/smallest-good-base/) 

2. **二分+dp**

3. **二分+差分**

**贪心+二分**  LIS 问题（动态规划专题讲解）




学习分享

二分的本质：
如果我们能够通过某种方式将一个区间划分成两个区间，左边区间满足某种特性；右边区间不满足某种特性。
那么我们就能够通过二分法来寻找左区间的右边端点或者右区间的左边端点
有单调性一定可以二分，但是二分不一定要有单调性

注意：配套讲解视频：B 站《百学原理》 - 二分法专题
注意：配套分析总结文章：二分法专题

整数二分

代码模板

浮点数二分

题目汇总

类型一：基本二分法题目（共 11 道）

浮点数二分例题

类型一：对结果进行二分（共 18道）

类型三 - min(max()) / max(min()) （共 6 道）

类型四 - 求最大平均值 / 最小平均值 (共 5 道)

类型五 - 求某种特殊的第 k 大 / 小（共 6 道）

其他涉及题目