Leetcode Array

二分

Template

# 左闭右开
def search(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid
    return -1

# 左闭右闭
def search(self, nums: List[int], target: int) -> int:
    left , right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid
    return -1

收敛位置证明 leetcode35

leetcode35.搜索插入位置。针对该问题，在搜索失败时收敛到哪个位置值得探讨。

证明问题 递增序列，采用左闭右开二分搜索，如果没有搜索到target，right的位置为target应该插入的位置。（其中left，right分别为左右区间下标；target为目标值，nums为序列）

证明过程 为了证明方便，首先我们初始化nums[right] == inf，在证明结论二，三中使用到。

结论一，在目标搜索不到情况下，退出循环的时候，left == right。假设退出循环left > right，则只可能通过上一步left = mid+1，则需要’mid >= right’。但事实上由于mid = (left + right) // 2，并且进入循环left < right，所以mid < right，与mid >= right矛盾，所以假设不成立。
结论二，在收敛过程中，nums[right] > target永远满足，已知一开始nums[right] > target，right在收敛过程中，使用表达式right = mid更新，且更新条件为nums[mid] > target，所以nums[right] > target永远满足。
结论三，在目标搜索不到情况下，nums[right]为第一个大于target的数。根据结论二，已知nums[right] > target，假设在right前面还存在比nums[right]小，但是大于target的数，则nums[right-1] > target。根据结论一，可知退出循环的时候left == right，则在上一轮循环，执行了left(right) = mid + 1 -> mid = right - 1 ，且执行条件为nums[mid] < target -> nums[right-1] < target，与假设相矛盾，故假设不成立。
结论四，在目标搜索不到情况下，退出循环的时候，right的位置为target应该插入的位置。根据结论三，可得结论四成立。

不严谨证明 （该证明不一定正确）上面的证明尽管成立，但是比较繁琐，对于实际使用不太友好。根据二分搜索，如果target存在于nums中，则会找到目标位置，否则在大多数情况下退出循环前的最后一个或两个迭代中left和right分别为第一个小于target的位置和第一个大于target的位置。因此在左闭右开情况下，mid = left -> nums[mid] < target,最后会执行left = mid + 1 -> left = right，left和right位置为target应该插入的位置。而在左闭右闭情况下，由于mid = left -> nums[mid] < target会执行left = mid + 1 -> left = right，接着由于mid = right -> nums[mid] > target，执行right = mid - 1，所以left和right位置互换，left和right分别为第一个大于target的位置和第一个小于target的位置。

Leetcode Array

目录

二分

收敛位置证明 leetcode35