【LeetCode 34】算法：在排序数组中查找元素的第一个和最后一个位置

题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

---

核心思路：

要解决这个问题，我们可以分两步进行：首先找到目标值 target 在数组中的起始位置，然后找到结束位置。
由于数组是按照非递减顺序排列的，可以使用二分查找算法来实现这个目标，二分查找的时间复杂度为 O(log n)。

算法步骤：

1. 查找起始位置：使用二分查找找到 target 的第一个出现位置。如果找不到，返回 [-1, -1]。

2. 查找结束位置：在找到起始位置后，继续使用二分查找找到 target 的最后一个出现位置。

复杂度分析：

时间复杂度：O(logn)
由于查找起始位置和查找结束位置是两个独立的二分查找过程，每个过程的时间复杂度都是 O(logn)。
由于这两个过程是顺序执行的，总的时间复杂度是 O(logn)+O(logn)=O(logn)。

空间复杂度：O(1)，只使用了常数额外空间来存储中间变量（如 left, right, mid 等）。因此，空间复杂度是 O(1)。

Java代码实现：

class Solution {public int[] searchRange(int[] nums, int target) {int[] result = {-1, -1};int left = 0, right = nums.length - 1;// 查找 target 的起始位置while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}// 检查是否找到 targetif (left < nums.length && nums[left] == target) {result[0] = left;// 查找 target 的结束位置left = 0;right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}result[1] = right;}return result;}
}