算法套路三_二分查找——红蓝染色法

开发运维 2023-08-13 竹子爱熊猫手机阅读

算法套路三:二分查找——红蓝染色法

套路示例：LeetCode34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二分查找本身并不复杂，但在写代码时往往会出现问题，比如出现死循环，不知道如何初始化，不知道为什么有时left=mid，有时left=mid+1，有时会莫名其妙把某个数排除，那么看完这个套路课你都懂了

首先是循环不变量以示例一为例： L和R分别指向询问的左右边界，即闭区间[L, R]M指向当前正在询问的数，且红蓝染色法，即左红右蓝若是升序排列则：

蓝色背景表示 true，即≥target
红色背景表示false，即= target 的 i 1. 如果数组为空，或者所有数都 < target，则返回 len(nums) 1. 要求 nums 是非递减的，即 nums[i] int: left, right = 0, len(nums) - 1 # 闭区间 [left, right] while left = target mid = (left + right) // 2 if nums[mid] List[int]: start = lower_bound(nums, target) # 选择其中一种写法即可 if start == len(nums) or nums[start] != target: return [-1, -1] 1. 如果 start 存在，那么 end 必定存在 end = lower_bound(nums, target + 1) - 1 return [start, end]
左闭右开区间写法
```
def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)  # 左闭右开区间 [left, right)
    while left < right:  # 区间不为空
        1. 循环不变量：left-1与right
        1. nums[left-1] = target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right)
        else:
            right = mid  # 范围缩小到 [left, mid)
    return left  # 或者 right
```
开区间写法
```
def lower_bound3(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)  # 开区间 (left, right)
    while left + 1 < right:  # 区间不为空
        mid = (left + right) // 2
        1. 循环不变量：left与right
        1. nums[left] = target
        if nums[mid] < target:
            left = mid  # 范围缩小到 (mid, right)
        else:
            right = mid  # 范围缩小到 (left, mid)
    return right  # 或者 left+1
```
- 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数），lower_bound返回下标
- 第一个大于等于x的下标： low_bound(x)
- 第一个大于x的下标：可以转换为第一个大于等于 x+1 的下标 ，low_bound(x+1)
- 最后一个一个小于x的下标：可以转换为数组中第一个大于等于 x 的下标 的左边位置, low_bound(x) - 1;
- 最后一个小于等于x的下标：可以转换为数组中第一个大于等于 x+1 的下标 的 左边位置, low_bound(x+1) - 1;