二分法开闭区间写法异同

主要分为四类：(以二分查找为例)

• 闭区间

• 左开右闭

• 左闭右开

• 开区间

left , right = 0 , n-1
while left <= right:
    mid = (left + right)//2
    if nums[mid]<target:
        left = mid + 1
    else:
        right = mid - 1
return left

left , right = -1 , n-1
while left < right:
    mid = (left + right)//2
    if nums[mid]<target:
        left = mid
    else:
        right = mid - 1
return right

left , right = 0 , n
while left < right:
    mid = (left + right)//2
    if nums[mid]<target:
        left = mid + 1
    else:
        right = mid
return left

left , right = -1 , n
while left+1 < right:
    mid = (left + right)//2
    if nums[mid]<target:
        left = mid
    else:
        right = mid
return right

tips

可以看到主要区别就是left，right的初始值，和mid是否+-1，
可以很简单地理解为，开区间就是把一个边界向外扩大了1，也
即相对mid更远了，因此所有计数都相应地外扩1