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

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

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

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

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

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

• 蓝色背景表示 true，即≥target
• 红色背景表示false，即= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 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]
# 如果 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:  # 区间不为空
          # 循环不变量：left-1与right
          # 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
          # 循环不变量：left与right
          # 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;

  套路总结

  红蓝染色法

  • left指针掌管左边蓝色区域，蓝色表示 truej即所求值及其右侧，right指针掌管右边红色区域，红色表示false即所求值左侧，两者互不冲突，通过不断向目标区域靠近，扩大两个指针的掌管区域，直到两者掌管的区域接壤
  • 使用闭区间时，L-1必定是红色即false，R+1必定是蓝色即true，这就是循环不变量
  • 关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质，即将区间外染成红色与蓝色。
  • 根据以上两点，在做题时关键即确定二分条件函数isBlue()，判断是否满足条件，满足条件则right 左移使右侧变蓝 ，不满足条件则left 右移使左侧变红

  代码规范

  • 注意代码区间开闭写法，之前提过的在LeetCode题解中大家看到的left与right取初值有时不一样，在二分时left指针有时等于mid+1有时等于mid，这是区间开闭的问题，不必纠结太多，三种都可以，我习惯于使用闭区间

  • 如果找不到比较元素，则可将数组最后一个元素单独提出作为比较元素，且right=n-2，因为若最后一个元素为所查找元素，二分查找时left也可以超出right=n-2的范围找到该元素；若不是所查找元素，单独提出也没有影响.

  • 根据上一点就明白为什么有时LeetCode题解在二分前就去掉了数组某个元素，这不会影响最终结果，可能是因为能判断这个元素不是所求结果，或者这个结果在最后一次循环时能够遍历到（闭区间时left能够遍历到数组长度+1）

  练习LeetCode162. 寻找峰值

  峰值元素是指其值严格大于左右相邻值的元素。
  给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。对于所有有效的 i 都有 nums[i] != nums[i + 1]
  

  已知nums[i] != nums[i + 1]，那么我比较nums[i] 与nums[i + 1]，且将最后一个元素提出，防止nums[i + 1]数组越界，而若该元素是峰值，left在最后一次循环时能是left=n-1找到，若不是峰值，则不需要遍历该元素

  func findPeakElement(nums []int) int {
  
      left:=0
  
      right:=len(nums)-2
  
      for left end && nums[i] >= target