在排序数组中查找元素的第一个和最后一个位置 题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [ -1, -1 ]。要求算法时间复杂度必须是 O(log n) 级别。 解题过程： 问题分析 由于数组是排序的，我们需要高效地找到目标值的起始和结束位置。O(log n) 的时间复杂度要求提示我们使用二分查找算法。但标准的二分查找只能找到一个位置，而我们需要找到两个边界位置。 解题思路 我们可以通过两次二分查找来解决这个问题： 第一次二分查找：找到目标值的起始位置（第一个等于 target 的元素） 第二次二分查找：找到目标值的结束位置（第一个大于 target 的元素的前一个位置） 详细步骤 步骤一：查找起始位置 初始化左指针 left = 0，右指针 right = nums.length - 1 当 left ≤ right 时循环： 计算中间位置 mid = left + (right - left) / 2 如果 nums[ mid] < target，说明目标值在右侧，left = mid + 1 如果 nums[ mid ] ≥ target，说明目标值在左侧或就是 mid，right = mid - 1 循环结束后，left 就是目标值的起始位置（需要检查是否越界且值确实等于 target） 步骤二：查找结束位置 重新初始化 left = 0，right = nums.length - 1 当 left ≤ right 时循环： 计算中间位置 mid = left + (right - left) / 2 如果 nums[ mid ] ≤ target，说明结束位置在右侧，left = mid + 1 如果 nums[ mid ] > target，说明结束位置在左侧，right = mid - 1 循环结束后，right 就是目标值的结束位置（需要检查是否越界且值确实等于 target） 边界情况处理 检查起始位置是否有效：如果 start > nums.length - 1 或 nums[ start ] ≠ target，说明目标值不存在 检查结束位置是否有效：如果 end < 0 或 nums[ end ] ≠ target，说明目标值不存在 如果目标值不存在，返回 [ -1, -1 ] 示例演示 以 nums = [ 5,7,7,8,8,10 ], target = 8 为例： 查找起始位置： 初始：left=0, right=5, mid=2 → nums[ 2]=7 <8 → left=3 第二轮：left=3, right=5, mid=4 → nums[ 4 ]=8≥8 → right=3 第三轮：left=3, right=3, mid=3 → nums[ 3 ]=8≥8 → right=2 循环结束，start = left = 3 查找结束位置： 初始：left=0, right=5, mid=2 → nums[ 2 ]=7≤8 → left=3 第二轮：left=3, right=5, mid=4 → nums[ 4 ]=8≤8 → left=5 第三轮：left=5, right=5, mid=5 → nums[ 5 ]=10>8 → right=4 循环结束，end = right = 4 最终结果：[ 3, 4 ] 复杂度分析 时间复杂度：O(log n)，因为进行了两次二分查找 空间复杂度：O(1)，只使用了常数级别的额外空间