写在前面
讲课课件配套资料。
课件下载地址：
链接：https://pan.baidu.com/s/1hiFYRS3MeE0Yms7r4cWTFA
提取码：fmj1
隐去了部分涉及个人隐私的部分。
概念+典例篇
二分法
指的是将一个整体事物分割成两部分。
也即是说，这两部分必须是互补事件，即所有事物必须属于双方中的一方，且互斥，即没有事物可以同时属于双方。
在 OI 中的应用：二分查找，二分答案。
二分查找
用来在一个 有序数组 中查找某一元素是否出现的算法。
以在一个升序数组中查找一个数为例，每次考察数组当前部分的中间元素。
- 若中间元素刚好是要找的，就结束搜索过程。
- 若中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需要到右侧去找就好了。
- 若中间元素大于所查找的值，同理，右侧的只会更大而不会有所查找的元素，所以只需要到左侧去找。
搜索过程中，每次都把查询的区间减半。
因此对于一个长度为 \(n\) 的数组，至多会进行 \(