admin管理员组

文章数量:1794759

【C++例题 / 训练】二分算法（模板 & 例题）

引言

二分也就是二分查找，又叫折半查找。这种算法正如其名，每一次都要分一半。

二分算法可以分为二分查找和二分答案。

以在一个升序数组中查找一个数为例，每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找

二分法的使用条件

二分法是适用于解决具有“二段性”(单调性)的问题的方法，通常表现为求解满足某一条件的最大值或者最小值

  1. 上下界确定。 我们可以通过上下界的折半来优化查找。
  2. 二段性： 对某一范围内的数据，存在一个临界点，使得临界点某一侧的所有数据都满足某一性质，另一侧的所有数据都不满足这一性质，就称这一范围内的数据具有二段性。

二段性包括单调性，即区间内有序，这样二分出来的结果是严格大于或者小于或等于target的。 但是，二段性也体现在非单调性上，也称为局部有序，可以参考 162. 寻找峰值 和 33. 搜索旋转排序数组。由这些题我们可以得知，二分法的奥义（本质）不在于单调性，而是二段性。也就是我们能对整体无序但局部有序的序列进行二分法。

二分的前提条件

1、答案在一个区间内（一般情况下，区间会很大，暴力超时） 2、直接搜索不好搜，但是容易判断一个答案可行不可行 3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。 4、若有多个答案满足题意，则这些答案具有如下特点：若答案 x 满足，则答案范围内小于 x 或大于 x 的答案均满足。

模板

本文标签： C例题训练二分算法（模板 amp 例题）

版权声明：本文标题：【C++例题训练】二分算法（模板 & 例题） 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754824642a1706929.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。