二分搜索 分析

二分搜索深入分析

二分小技巧

我们考虑二分问题 区间应该如何收缩的问题时
应该把nums[mid]直接想象成数组中间的位置的数 （这句话好像是废话，但是确实应该这么思考...）
固定了中间位置的数字之后 分析target跟nums[mid]的关系
target比较大 所以target在右半段 反之 target在左半段

还是示意图直观

image image

class Solution:
    # 基本的二分搜索 查找特定的数字是否存在
    def binarySearch(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid + 1
            elif nums[mid] < target:  # 代码走到这一行 说明了mid一定不是target 之后的搜索区间一定不需要包括mid
                left = mid + 1
            else:
                right = mid - 1
        return -1

    def binarySearch2(self, nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target: # target 位于右半段
                left = mid + 1
            else: # num[mid] <= target
                right = mid # 因为nums[mid] == target 是可能的 所以mid这个位置不能丢
        return right if nums[right] == target else -1 # 有可能target不存在

对于这两段代码的分析

对于基本的二分搜索

• 每一轮循环区间都必然会收缩 所以算法必然收敛
• 如果nums中没有target left ， right指针必然会交叉

对于有重复元素的二分搜索

• 不能保证每一轮搜索区间的收缩
  因为当nums[mid]<=target时 right = mid 区间可能不会收缩
• 当 left == mid == right 并且 nums[mid] < target代码陷入死循环
  所以循环条件不能是while left <= right