...
整体思路刚好与 searchLeft 相反，为收缩左边届 ——
方法二：利用 leftBound
上一题的 searchLeft 中其实隐含了一个「找到 >= target 的最小索引」的方案（称为 leftBound）
...
| Code Block | ||
|---|---|---|
| ||
func searchRange(nums []int, target int) []int {
l := searchLeft(nums, target)
if l == -1 {
return []int{-1, -1}
}
r := searchRight(nums, target)
return []int{l, r}
}
func searchLeft(nums []int, target int) int {
x := leftBound(nums, target)
if x >= len(nums) || nums[x] != target {
return -1
}
return x
}
func searchRight(nums []int, target int) int {
// 寻找 target 的右边界 = 寻找 >= target+1 的元素的左边届-1
x := leftBound(nums, target + 1) - 1
// 注意此时 target+1 过小时，x = -1
if x == -1 || nums[x] != target {
return -1
}
return x
}
// 返回 >= target 的最小索引
func leftBound(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
return right
} |
LCCN LCR 172. 统计目标成绩的出现次数
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/
本题与上一题几乎一样（只有返回值不一样）
采用 rightBound 完成：
| Code Block | ||
|---|---|---|
| ||
func countTarget(scores []int, target int) int {
l := searchLeft(scores, target)
if l == -1 {
// score not exist
return 0
}
r := searchRight(scores, target)
return r-l+1
}
func searchLeft(nums []int, target int) int {
x := rightBound(nums, target-1) + 1
if x >= len(nums) || nums[x] != target {
return -1
}
return x
}
func searchRight(nums []int, target int) int {
x := rightBound(nums, target)
if x < 0 || nums[x] != target {
return -1
}
return x
}
// 返回 <= target 的最大索引
func rightBound(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] <= target {
left = mid + 1
} else{
right = mid
}
}
return left - 1
} |
LC.278 First Bad Version 第一个错误的版本
...