【力扣打卡系列】二分查找（红蓝染色法）

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day8

在排序数组中查找元素的第一个和最后一个位置

• 题目描述
• 解题思路
  • 二分查找
    • 注意勿漏循环，条件为left <= right
    • 注意比较的是nums[mid]与target的值，不是mid
    • 注意if start == len(nums)|| nums[start] != target，两个条件缺一不可
    • 如何找end：找到大于等于target+1的第一个位置，即find(nums,target+1)，再-1就好
• 代码参考

func find(nums []int, target int) int{
    left := 0
    right := len(nums) - 1
    for left <= right{
        mid := left + (right - left)/2
        if nums[mid] < target{
            left = mid + 1
        }else{
            right =mid - 1
        }
    }
    return left
}

func searchRange(nums []int, target int) []int {
    start := find(nums,target)
    if start == len(nums)|| nums[start] != target{
        return []int{-1,-1}
    }
    end := find(nums,target+1) - 1
    return []int{start, end}
}

• tips
  • • 循环不变量
      • 升序数组
      • 红色：小于target；蓝色：大于等于target
      • 需要保证：L-1永远指向红色，R+1永远指向蓝色
      • 根据循环不变量
        • R+1是最终要找的答案（第一个满足大于等于target的位置）
        • 同时因为循环结束后R+1=L，所以答案也可以用L表示
      • 升序旋转数组（拆成两段升序）
        • 将mid与最后一个数比较
          • 小于最后一个数就是蓝色（min（target）及min（target）右侧）；否则就是红色（在min（target）左侧）
      • 搜索升序旋转数组（拆成三段升序 ）