查找首尾位置 · 两道闸门 lowerBound

怎样从“升序数组 nums=[5,7,7,8,8,10]，找 target=8 的首末下标。”推导出 二分查找 · 双边界闸门，并证明每次状态变化都不会漏掉答案？

中心结论：普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

在本站主例中，升序数组 nums=[5,7,7,8,8,10]，找 target=8 的首末下标。

算法最终需要得到或观察：8 占据下标 3 到 4，返回 [3,4]；target=6 时返回 [-1,-1]。

线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“有序区间闸门”，明确答案需要观察什么。
2. 2状态只维护 两趟 lowerBound 各自的 lo/hi/mid、闸门落点、以及不存在检查。
3. 3转移每一步按照 普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。
4. 4收尾读取 8 占据下标 3 到 4，返回 [3,4]；target=6 时返回 [-1,-1]。，并复核边界与复杂度。

二分的核心不是 mid 公式，而是左右哪一侧可以被证明不含答案。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：两趟 lowerBound 各自的 lo/hi/mid、闸门落点、以及不存在检查。

给出一个有序数组 `nums` 和一个数 `target`，要求在数组中找到第一个和这个元素相等的元素下标，最后一个和这个元素相等的元素下标。 这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种题： 1. 查找第一个值等于给定值的元素 2. 查找最后一个值等于给定值的元素 3. 查找第一个大于等于给定值的元素 4. 查找最后一个小于等于给定值的元素

这一题的解题思路可以分别利用变种 1 和变种 2 的解法就可以做出此题。或者用一次变种 1 的方法，然后循环往后找到最后一个与给定值相等的元素。不过后者这种方法可能会使时间复杂度下降到 O(n)，因为有可能数组中 n 个元素都和给定元素相同。(4 大基础变种的实现见代码)

普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。

执行过程中持续维护：两趟 lowerBound 各自的 lo/hi/mid、闸门落点、以及不存在检查。

正确性依赖以下不变量：相同值连续排列，两道闸门正好夹住这一段。；下界二分：lo 左边都 < targetForSearch，lo 及右边都 >= targetForSearch。

面试时可以压缩为：我不会用普通二分找到一个 target 就停，因为题目要的是 target 的完整区间。由于数组有序，相同元素一定连续，所以我把问题拆成两个 lowerBound：第一个 >= target 的位置是左边界，第一个 >= target+1 的位置是右边界后一个位置。最后检查左边界是否真的是 target，不是则返回 [-1,-1]。整体时间 O(log n)，空间 O(1)。

落到当前题，执行机制可以压缩为：普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目输入我们要找的不是任意一个 8，而是整段 8 的左端和右端。 因为：普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。
2. 2普通二分命中 mid=4普通二分找到一个 8 就满足了，但题目要首末两个下标。 因为：index=4 是 8，但无法确定左边 index=3 的 7…不对，index=3 也是 8。
3. 3左闸门 lowerBound(8)第一趟找左墙：第一个 >= target 的下标。 因为：这就是左边界——target 段的起始位置。
4. 4左闸门 lo=2, hi=3index=0,1 都 <8，连同 mid=1 一起排除。 因为：下界二分里 < 时 lo=mid+1，向右找第一个 >=8 的位置。
5. 5右闸门 mid=3index=3 仍是 8，不可能是 >=9 的位置，连同左侧排除。 因为：右闸门要找第一个 >=9，8 都太小。
6. 6右闸门 R=5右墙后一格确认：8 段紧挨 index=5 之前结束。 因为：第一个 >= target+1 的位置之前一格，正是最后一个 target。
7. 7target=6即使 target 不存在，lowerBound 也会返回一个合法下标。 因为：所以必须额外检查 nums[left] 是否真的等于 target。
8. 8返回 [-1,-1]不存在时一次 lowerBound + 检查就够了。 因为：这是 LC34 与普通 lowerBound 题（如 LC35）的关键区别。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func searchRange(nums []int, target int) []int {
	return []int{searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)}

}

// 二分查找第一个与 target 相等的元素，时间复杂度 O(logn)
func searchFirstEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == 0) || (nums[mid-1] != target) { // 找到第一个与 target 相等的元素
				return mid
			}
			high = mid - 1
		}
	}
	return -1
}

// 二分查找最后一个与 target 相等的元素，时间复杂度 O(logn)
func searchLastEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] != target) { // 找到最后一个与 target 相等的元素
				return mid
			}
			low = mid + 1
		}
	}
	return -1
}

// 二分查找第一个大于等于 target 的元素，时间复杂度 O(logn)
func searchFirstGreaterElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] >= target {
			if (mid == 0) || (nums[mid-1] < target) { // 找到第一个大于等于 target 的元素
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// 二分查找最后一个小于等于 target 的元素，时间复杂度 O(logn)
func searchLastLessElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] <= target {
			if (mid == len(nums)-1) || (nums[mid+1] > target) { // 找到最后一个小于等于 target 的元素
				return mid
			}
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

func main() {
    // 1. 主例
    //    输入：mode="first-last", array=[5,7,7,8,8,10], target=8
    //    期望：8 占据下标 3 到 4，返回 [3,4]；target=6 时返回 [-1,-1]。
    //
    // 2. 失败 / 未命中
    //    检查：找到一个 target 就返回，无法保证是第一个或最后一个。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC35 搜索插入位置；LC704 二分查找
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意升序数组 nums=[5,7,7,8,8,10]，找 target=8 的首末下标。
2. 2重复线性扫描没有利用判定条件的单调性；二分每次用一个判断安全排除一半候选。
3. 3优化普通二分找的是一个点，LC34 找的是一段区间。重复元素在排序数组中一定连续，所以我们只要找到这段连续区域的左墙和右墙。左墙是第一个 >= target 的位置，右墙后一个位置是第一个 >= target+1 的位置。
4. 4证明相同值连续排列，两道闸门正好夹住这一段。；下界二分：lo 左边都 < targetForSearch，lo 及右边都 >= targetForSearch。
5. 5复杂度时间 O(log n)，空间 O(1)