刚开学一周，事还是比较少，一周多点的时间把灵神的二分题单刷完了（当然有些关于图的题目只能含泪放弃 ...）
一周的时间，对于二分算法本身有了更加深入的理解。下面分享一下收获与感悟。

• 首先讲讲这个算法本身的写法：
  
  本人比较喜欢灵神介绍的二分查找的闭区间写法。但是可能相比于闭区间，开区间写法更容易记忆（不需要考虑 +1 / -1）
  

  说完整体解法大框架的分类，下面根据具体实现细节的顺序谈一谈需要注意的点（其实是我曾经没有弄清的地方）：
  

  1. 首先我们要初始化 left 和 right 指针：
     
     一般来说，left可能为 {-1, 0, 1}，right一般从数组元素最大值，数组元素和等方面考虑
     但是需要注意的是初始化的值，会由于开闭区间写法的不同而有细微差异
     
  2. 接着谈谈自己对 int mid 写法的理解：
     
     本来其实一直以为 int mid = (left + right) / 2 和 int mid = left + (right - left) / 2 两个写法是没有区别的
     （虽然大神们都是用后一种写法，但是前一种也见人用过，而且大部分时候都是可以通过的）
     但是刷完这部分题单下来，发现了前面一种可能会有的两种错误：
     

  • 第一，当left, right有负数时结果好像会不准确

  • 第二，大部分题目会有这个要求：1 <= n <= 2^31 - 1, 那么采用前一种时往往要强制类型转换，因为相加可能会溢出
    

  3. 再而就是我之前会弄不清 return 值：
     
     求最大与求最小容易写混，开闭区间的返回值一个是 right，一个是 left，等等诸如此类的问题
     
     也许提高训练与熟练度后可以有效避免这些问题，但是可能相比于单纯相信自己的熟练度，不如花个两秒想一下循环不变量是什么
     
     比如 left 一侧还是 left - 1 一侧恒为true，当跳出while循环后 left 和 right 之间满足什么条件，各自的循环不变量是什么
     
     但是目前还是有比较困惑的地方，就是一般题目会另说，若无满足条件的值 return -1，本人只会在一开始进行一次特判，还无法做到让答案直接在二分中得到统一

• 接着谈谈二分算法的题目一般会让我们做什么：
  
  大多数简单题目，比如有序数组相关的都是可以借助 lower_bound 或者 binary_search 函数直接实现，不需要手搓算法
  
  但是对于很大一部分问题，都是自己在 main 函数中搭好二分框架，然后自己另写一个 check 函数 （后面会详细谈谈对此的理解）
  
  然后除了常见的检验 target 值的存在性，target 值所在索引外，还可以找到类似于第 k 大的元素等等
  
  看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路

  
  

• 然后聊聊什么时候用二分算法：
  
  二分真正的难点在于不知道什么时候用，如果不是这道题出现在了灵神的二分题单中或者碰巧看见了二分查找的标签，我们很容易就会被题目复杂的信息引诱进去，然后开始思考比较复杂或者错误的方向
  
  本人也想细讲一下如何确定什么时候使用二分，或者说二分的优势到底在哪。
  

  • 一是时间复杂度上，O(logN)，不必多提（题目若有要求完成O(logN)时间复杂度，那大概率是二分)。
    
  • 二是对于一些题目而言，题目设定会比较复杂，或者其背后的代数背景比较复杂。我们直接根据数据，通过数学方法证明出答案与数据之间的关系可能性不大，如果可以也会花费很多时间。因此与其将其做成一道数学证明题或者代数分析题，我们不妨将其做成一道验证题。
    就像大家做数学选择题一样，当然可以直接根据题干条件得出结果，但是当然也可以根据选项反向验证得出答案。而我以为，二分答案的方法便是基于这种思想，将复杂的数学问题，用极小的时间代价转换为验证题，这样题目难度会大大降低（关键都转换为 check 函数的实现）

  
  对于适用性而言：
  一开始觉得二分算法只适用于有序性的数组数对
  后面慢慢发现，实际上只要答案（或者是可以求出答案的间接值）是唯一的，满足两段性的（即 <= ans 不符合题意，> ans 符合题意，反之亦然），就可以用二分算法寻找答案，所作的只是检验当前值是否符合题意即可
  再后来无意间看到三叶姐的一句话（是在一个有关旋转元素可重数组的问题中）让我茅塞顿开，分享给大家：

  • " 我们进一步发现「二段性」还能继续细分，不仅仅只有满足01特性（满足/不满足）的「二段性」可以使用二分，满足1? 特性（一定满足/不一定满足）也可以二分 "
    

• 最后是一点杂谈：
  
  二分算法实现本身很简单，但是其应用的时机以及应用时的思想值得深思。
  然后特意提一嘴自己做的最快乐的一题：2982，在实现check函数时使用了双指针中的分组循环，虽然不是最优解法，但是非常爽！！！

  
  

以及接下来准备开始刷灵神第三个题单 —— 单调栈了，不知道接下来的日子学校里会忙不忙 :)

以及捞一捞愿意一起刷题或者学些新东西的搭子！！！
虽然本人刚刚起步，水平糟糕 :(
But I am always willing to learn something new ! ! !