高级农民
- 积分
- 2661
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-1-6
- 最后登录
- 1970-1-1
|
我其实也有跟楼主类似的困惑，正好在突击刷Binary search tag，就整理一下一点个人理解，希望能抛砖引玉。可能有点啰嗦冗长，请多包涵。
1. pivot/mid index
感觉这个相对好梳理一些，以Python 3为例有如下模版：
mid = (left + right) // 2
mid = int((left + right) / 2)
mid = (left + right) >> 1 # bitwise operation --> 好处是比除法运算快
以上共同的缺点是：如果（left+right）超过最大可存的整数（i.e. integer overflow），那么就有bug，可以用如下模版应对：
mid = left + (right - left) // 2 # 如果left和right都没有over，那么（right - left）也就不会。
mid = left + ((right - left) >> 1) # 同上，另外此处用bit operation运算比较快。综合来说应该是最好的选择，这个就是之前一个层主推荐的。BTW，mid = left + (right - left) >> 1有bug，因为这等同于(left + (right - left)) >> 1。
还有时候用法是: mid = left + (right + 1 - left) >> 1，这个区别可看个人喜好了，但算是个小细节吧，有时候情急之下debug可能会有帮助。
| Example | left=0, right=0 | left=0, right=1 | left=0, right=2 | left=0, right=3 | | mid = left + （(right - left) >> 1） | mid=0 | mid=0 | mid=1 | mid=1 | | mid = left + （(right + 1 - left) >> 1） | mid=0 | mid=1 | mid=1 | mid=2 |
所以，mid = left + (right - left) >> 1的到的mid要么在left和right正中间，要么更靠近left。这种情况下，如果while loop里面二分法的时候left=mid的话，那就会有infinite loop的bug。同理，用mid = left + (right + 1 - left) >> 1的话，如果right=mid，那么也会bug。
2. Binary search模版和思路
楼主提到的
“int left = 0, right = nums.length;
有时又看到，right = nums.length -1;
while loop里，有时left < right 有时left <=right ;”
这几个情况在Leetcode的Explore Card - Binary Search提到的三个模版中的前两个，也是我个人现在最常切换使用的两个模版。我也刷了不少上面的examples才摸出点感觉，有的题可能有一个模版更简洁一些，有的题用两种都差不多。感觉思路决定模版，模版代表思路，所以举个例子来比较一下不同模版/思路。
Leetcode 35: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
模版1: l, r = 0, n & while l < r
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n
while l < r:
m = l + ((r-l) >> 1)
if nums[m] == target:
return m
elif nums[m] < target:
l = m+1
else:
r = m #这里不能换成r=m-1，因为m此时还有可能是solution，所以不舍去
# at this point, we have l == r
return r
思路：
- 初始r=n是为了保证初始search space [l, r]包含target solution；如果r=n-1，那么不能保证初始search space还能一定包含solution（e.g. solution=n的时候）。
- 二分操作l=m+1和r=m之后，也都仍然保证solution还在剩余的half search space里。这样可以用induction证明search space无论怎么二分，之后剩下的search space都肯定包含solution。这个结论下面会有用。这也解释了为什么不能把r=m替换成r=m-1，因为m目前仍有可能是solution。
- 感觉如果写出的代码如果能完全满足这个inductive logic的话，可能是最自然的方法（之一）了。
- 因为用了while l < r，被二分操作的最小的search space是size=2（i.e. l and r相邻）。同时，最后跳出while loop后，terminal condition是l==r，剩余search space是[r]，这个item r从来没有被二分法检验过。但我们知道/证明了那就是solution，所以可以直接return r这个结果。
模版 2: l, r = 0, n-1 & while l < r
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n-1
while l < r:
m = l + ((r-l) >> 1)
if nums[m] == target:
return m
elif nums[m] < target:
l = m+1
else:
r = m # 如果此处换成r=m-1也可以work，但是是另一种思路，解释请见下面
# at this point, we have l == r
if nums[r] >= target:
return r
else:
return n # or r+1
思路：
- 区别于模版1，这里用了初始r=n-1，导致不能直接用刚才induction证明的结果，因为初始search space并不一定包含solution。所以只有在“solution在l, r初值之间”的情况下，之后二分操作才能保证remaining search space contains the solution。“solution不在l, r初值之间”的情况还需要另外考虑。
- 另一种角度分析就是，这里的二分操作只能保证discarded space does not contain the solution，如果通过二分检验把所有不含solution的部分都舍弃了，那么还需要检验最后剩下的search space才能得到solution。
- 相同于模版1，因为用了while l < r，最后terminal condition还是l==r。
- 结果就是，最后while loop结束后，剩余一个item r没检验过，不知道是否是solution，所以要额外检验（i.e. solution=n的特殊情况），代码稍微长一点。
- BTW，这里如果把r=m换成r=m-1也还能work，但是不能保证discarded space does not contain the solution，因为m有可能是solution。但如果m确实是solution，又被discard了话，那么意味着r=m-1以后的r满足nums[r] <= target，所以r在之后的循环里不会再改变了，于是代码最后那个return r+1的还能account for这个情况的solution。在while loop外的检验也能照顾到nums[r]==target的情况。如果之前没用过这个思路的话，可能需要花点时间想清楚。
模版 3: l, r = 0, n-1 & while l <= r [Leetcode 35 答案]
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n-1
while l <= r:
m = l + ((r-l) >> 1)
if nums[m] == target:
return m
elif nums[m] < target:
l = m+1
else:
r = m-1 # 这里不能换成r=m，不然当l+1==r时，配合m = l + ((r-l) >> 1)，会陷入infinite loop。
# at this point, we have l == r+1
return r+1 # or l
思路：
- 这里和模版2都用了r=n-1，但区别在于这里while l <= r。
- 区别：因为用了while l <= r，最后terminal condition是l==r+1。
- 跟模版2的r=m-1情况分析起来一样，这个模版里的二分法既不能保证discarded space does not contain the solution，也不能保证remaining search space contains the solution。但again，如果m确实是solution，又被discard了话，那么意味着r=m-1以后的loop里的r满足nums[r] <= target，所以r在之后的循环里不会再改变了，于是代码最后那个return r+1的还能account for这个情况的solution。
- 再看discarded space does not contain the solution的情况，就又和模版2的思路一样：舍弃不含solution的space，剩余的search space再作分析/检验。
- 但这里不像模版2那样需要在while loop结束后再做额外的check。得益于while l <= r，被二分操作检验的最小的search space是size=1（i.e. l and r相同），所以所有的item都被while loop内的二分法检验过；while loop结束后剩余的search space为空集，无须再检验。
- 另外，对于solution=n的特殊情况，r会一直保持初值n-1不变，所以return r+1可以照顾到这个特殊情况。
模版 4: l, r = 0, n & while l <= r
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
l, r = 0, n
while l <= r:
m = l + ((r-l) >> 1)
if m == n:
return n
if nums[m] == target:
return m
elif nums[m] < target:
l = m+1
else:
r = m-1
# at this point, we have l == r+1
return r+1 # l # or m
思路：
- 这个思路基本跟模版3本质上一样。细微的区别在于这里用了r=n初值，但没帮上啥忙，反倒需要在while loop里要考虑到m==n的情况，提前输出结果，以免后面nums[m] index out of range.
写完发现有点太长了，抱歉。。。总结一下，感觉选模版关键在于选以下哪种思路：
- remaining/current search space always contains solution
- discarded search space does not contain any solution
- if the solution is discarded by binary search/bisection, we could tell where it is relative to left or right bound. When the solution is not discarded, we're back to case 1 or 2
|
|
楼主: RELAY2014
狗仔卡
