学会二分法有这一篇就够啦！

  本文由blue撰写于2024年9月，深入讲解二分法这一基础但不简单的算法。文章从二分法的两大经典应用场景——二分查找与二分答案出发，详细解析其原理与实现。通过实例代码（如LeetCode第704题）和竞赛题目，探讨了不同区间定义（左闭右闭、左闭右开）下的实现方式，并延伸到寻找目标值首次/最后出现位置及二分答案的实际应用。适合初学者系统掌握二分法的核心思想与技巧。

  二分法是大家耳熟能详的基础算法，但是二分法，可没有你想像的那么简单，本篇将从二分法的两个经典利用场景——二分查找和二分答案，来讲懂二分法。

  二分法应用在一串有序的序列中，查找一个我们所需要的值，注意一定是有序的序列。

  比如说两个人玩猜数字游戏，1-10000，A心中想一个数，B来猜，B每次猜一个数，A都会回答他大了还是小了，这样B每次都可以折半的缩小查找的区间，这样就比直接把数从1数到10000要快很多。

  很多教学都让大家背二分法的模板，我不这样认为，因为二分法是一个非常好理解的算法，所以用不着背模板，而是要理解算法的过程知道代码是怎么写的，这样才可以熟练的掌握二分法。

  我推荐的写法是根据左闭右闭区间的方法来写，下面是二分法的左闭右闭区间的代码

  再次强调：你进入while循环的条件一定要符合你的区间，也就是说你更新的区间一定要与你一开始查找的区间类型一致。

  你一开始是[left,right]（左闭右闭），你更新完还得是左闭右闭；！！！

  有了固定好区间的思想，你在写二分法的时候，才不会搞不懂，到底是应该left=right，还是leftright，其实都是可以的，只是后者是左闭右开区间，对应的区间变化，也应该符合左闭右开区间的规则。

  我在这里给出了左闭右闭，和左闭右开区间的两种写法，如果对此前讲解有不理解的同学能结合以下代码再体会以下。

  如果你成功的用两种不同的区间，写出了这道题，那么恭喜你，搞明白了区间与while循环判断条件的关系，接下来就要看一些比较特殊的二分查找：

  由于我们查找的有序序列元素可能还是重复的，那我们该如何去找第一个符合标准要求元素出现的位置呢？请看如下解释：

  代码中用ans来表示查找到元素的位置，与原来二分查找不同的是，这里找到目标值后并不直接退出，而是你要找在这个已经找到的目标值的位置的左边还有没有target，所以用先ans记住这一个位置，然后r=mid-1查找左边还有没有目标值，这样就能够找到元素第一次出现的值了。

  查找元素最后一次出现的位置也很简单，那就是先用ans记住当前位置，然后l=mid+1 查找右边还有没有目标值，这样就能够找到元素最后一次出现的位置。

  其实二分答案和二分查找中找元素第一次出现的位置，和最后一次出现的位置的思想非常的像！

  题目大意：让我们找到一个尽可能高的高度（因为这样砍的树少），然后得到至少等于M的木材

  这题我们对答案（也就是砍树的高度）进行一个二分搜索（只要这个高度下所得到木材=M,那他就是一个合法的高度），题目的要求是你找到一个合乎条件的答案，并不是直接输出这个答案，而是让这个值尽量大，所以你找到在这道题中ans=m都是合乎条件的，所以你每找到一个合乎条件的，就先把他记录下来，然后再往他的右边找，那就是l=mid+1;

  恭喜你已经做到这里了，我们趁热打铁来看看两道竞赛真题，这两题都有非二分的做法，但我个人觉得二分的做法更易于理解

  题目大意：炉子有一个称作转换率的属性V，V是一个正整数，这在某种程度上预示着消耗V个普通金属O恰好可以冶炼出一个特殊金属X

  每条记录中包含两个整数A和B，这表示本次投入了A个普通金属O，最终冶炼出了B个特殊金属X。

  （每条记录都是独立的，这在某种程度上预示着上一次没消耗完的普通金属O不会累加到下一次的冶炼当中。）

  小蓝有k种卡片, 一个班有n位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。

  (1,1) (1,2) (1,3) (1,4) (1,5) (2,2) (2,3) (2,4) (2,5) (3,3) (3,4) (3,5) (4,4) (4,5) (5,5) 牌的种类，可以构成的牌组合的总数，其实是一个等差数列 比如说有3种牌 那就可以构成 [(1+3)*3]/2=6,6种不同的组合，就可以分给6位同学。 所以题目给定同学的数量，我们就找最少几种牌，构成的组合总数，可以容纳这些同学， 这样就把问题演变成了，查找最少种类牌，那就可以用到二分答案

  【数据结构】深入浅出讲解计数排序【图文详解，搞懂计数排序这一篇就够了】

  【数据结构】深入浅出讲解计数排序【图文详解，搞懂计数排序这一篇就够了】

  【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

  【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

  canceling statement due to conflict with recovery

  新能源汽车超级电容和电池能量管理系统的simulink建模与仿线D建模新境界：分布式软总线