二分法小结

老生常谈的问题。每次写稍微变化点的二分总还是要花点时间理下index，故总结下。欢迎提意见。

1）min < max, min <= max 的应用区别：
min < max 终止后元素尚未检查完要检查min/max;  max <= max 终止后无需检查min/max；

2）min/max= mid or mid +/- 1 的区别：
只剩两个元素的情况来讨论， 如果mid落在min这边，如果min = mid，target > mid 进入死循环，故min总需要min = mid + 1;
只剩一个元素的情况来讨论， mid = max， mid = min 均可能进入死循环；所以这种情况必然需要 min < mid；

重复元素找两边：
我们希望锁定最后一个元素，故：min < max后，最后来判定min的大小；
找最左边 max = mid - 1 or mid不重要；找最右边的反之亦然，但找最右边的integer有个技巧就是找最左边的target + 1，然后利用min来比较。

延伸技巧/思考：
1）使用while判断min + 1 < max后分别判断min/max，思路会更清晰，但代码会更笨拙。其实可以简化为min < max后只判断min。
2）中途终止，比如在找最左边元素的时候可以在循环内判断nums[mid] == target & （mid > 0 & nums[mid-1] != target)。这样退出循环后只需考虑不存在此元素的情况。
3）对于更复杂情况，nums[mid] == value单独开设条件分支，类似2）。

某章讲的方法更好些。
min + 1 < max
外加最后对 两个 corner case 判断。

我用这样的一个模板刷了大概LC八成以上的二分法题目。这能找到符合函数条件的最小index，找不到会返回数组的长度，范例为LC34

1. def searchRange(self, nums: List[int], target: int) -> List[int]:
   
2.         
   
3.         def bsearch(arr, condition):
   
4.             left, right = 0, len(arr)
   
5.             while left < right:
   
6.                 mid = (left+right)//2
   
7.                 if condition(arr[mid]):
   
8.                     right = mid
   
9.                 else:
   
10.                     left = mid + 1
    
11.             return left
    
12.         
    
13.         l = bsearch(nums, lambda x: x >= target)
    
14.         if l == len(nums) or nums[l] != target:
    
15.             return [-1, -1]
    
16.         r = bsearch(nums, lambda x: x > target)
    
17.         return [l, r-1]

复制代码