【力扣打卡系列】二分查找(红蓝染色法)
坚持按题型打卡&刷&梳理力扣算法题系列,语言为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)左侧)
- 将mid与最后一个数比较
- 搜索升序旋转数组(拆成三段升序 )
- 循环不变量
-