二分
二分搜索 Binary Search
关于有序数组中的二分查找及其衍生题，我一直觉得麻烦的不是思想，而是细节。leetcode比赛分数上不去，和OJ大佬相比，不是题目做少的问题，而是缺少沉下心来反思和总结。这两天刚好看到灵神的基础算法系列视频，想着最近也没啥事，反刍一下顺便写个笔记。
二分的模版一般有三种：有全闭区间的[left, right]，左闭右开的[left, right)，还有全开区间的(left, right)。每一种特点不同，循环里判断条件也不同，很看个人口味。我比较懒，觉得模版太多比较烦，也记不住，第二种最通用，所以我比较喜欢，以后碰到相关的题基本都按照这个套路写。力扣33题是一道使用二分的基础题，这里写了之后配合灵神的讲解视频，记录下几个比较有用的点：
- 要点一：
转化，>, <, <= 啥的都可以转化为 >=，比如找数组中 >x 的元素开始位置：lower_bound(a, target+1)；找 <x 的元素结束位置：lower_bound(a, target) -1；找 <=x 的元素结束位置：lower_bound(a, target+1) -1；
- 要点二：
二是用左开右闭的时候一般都要后处理，因为可能找不到啥的，这里循环结束时肯定是left==right，所以到底选left还是right也不用为难了，随便拉一个判定下答案符不符合要求就行了，少了麻烦
- 要点三：
二分要是一般用java/c++/golang啥的可能在取mid时候会溢出，可以这样写 mid = left + (right-left)/2，但我刷题一般用python哈哈哈
这道题我也是用[left, right)左闭右开写的，因为这道题肯定有答案所以不用后置处理。而且这里题目里数全是不同的，所以已经很方便了，不需要额外多处理。这里 nums[mid] < nums[right] 写成 nums[mid] < nums[-1] 也是可以的，反正就是通过对比mid处的数和另一个数，这个数只要能够帮助二分就行。
这题是153的进阶，多了一个数组中的数字可以重复，所以最坏情况下退化为线性搜索，没了O(log n)的效率，不过这不是啥问题。
- 要点一
注意这里因为数字可以重复，所以要是找原数组最右边的数字nums[-1]比较不行了，因为当 nums[mid] == nums[-1] 时，需要去掉mid和right指向的两个重复数字中的一个（因为保留一个就等于也保留了这个数是答案的可能），这里用脚想也知道不能去掉mid，所以只能去掉right指向的那个数，不然循环就推进不下去了。而right一变，要是下次比较还和nums[-1]比，那就错了。
这里主要是多了个mid和mid+1两个数的比较，一般题目就是用到mid，所以用到mid+1时可能会溢出，这里把right在初始化的时候-1，这样的话，之要进了while循环，里面的mid和mid+1就肯定是合法的，不用担心下标非法。至于本题答案是肯定存在的，所以不需要后处理。
这题吧，两次二分和一次二分都行。不过感觉灵神这种一次二分的处理更好更有意思，之后把二分判定逻辑写成函数肯定更通用，所以更偏向于第二种解。另外视频里灵神是用全开区间，即 (left, right)，所以初始化和中间指针的时候会和我的不一样，不过我还是喜欢我自己这种，无所谓了。
总结：
二分感觉还是挺搞的，细节比较多，比较烦，但这么一梳理，感觉还行，以后就用左闭右开模版了 [left, right)。希望下次遇到相似的题不再怵了。
