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

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

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

示例 1：

输入：nums = [`5,7,7,8,8,10]`, target = 8
输出：[3,4]

示例 2：

输入：nums = [`5,7,7,8,8,10]`, target = 6
输出：[-1,-1]```


示例 3：

输入：nums = [], target = 0 输出：[-1,-1]

 

## 题目解析

**题意总结**：
- 给定一个**已排序**（升序/非递减）的整数数组 `nums` 和一个目标值 `target`。
- 数组中可能包含重复的元素，你需要找出 `target` 在数组中第一次出现的位置和最后一次出现的位置。
- 如果找不到，返回 `[-1, -1]`。
- **强制要求**：算法的时间复杂度必须是 $O(\log n)$。

**核心考点**：
看到“已排序数组”和“$O(\log n)$ 时间复杂度”，毫无疑问必须使用**二分查找**。普通的二分查找只能保证找到目标值，但不能保证是第一个还是最后一个。因此，我们需要对标准的二分查找进行改造，分别去寻找**左边界**（第一个位置）和**右边界**（最后一个位置）。

## 解题思路

为了在 $O(\log n)$ 的时间内解决问题，我们可以进行**两次二分查找**：
1. 第一次二分查找：寻找目标值出现的**第一个位置**（左边界）。
2. 第二次二分查找：寻找目标值出现的**最后一个位置**（右边界）。

### 如何寻找左边界（第一个位置）？
在常规的二分查找中，当 `nums[mid] == target` 时，我们会直接返回 `mid`。
但为了找左边界，当我们发现 `nums[mid] == target` 时，我们**不应该立即返回**，因为当前位置可能不是第一个。正确的做法是：**记录当前位置，并继续在左半区间搜索**（即将右边界收缩为 `right = mid - 1`），看是否还有更靠左的 `target`。

### 如何寻找右边界（最后一个位置）？
同理，为了找右边界，当我们发现 `nums[mid] == target` 时，我们要**记录当前位置，并继续在右半区间搜索**（即将左边界收缩为 `left = mid + 1`），看是否还有更靠右的 `target`。

### 代码复用优化
因为寻找左边界和右边界的逻辑非常相似，只有在 `nums[mid] == target` 时的处理有所不同。我们可以提取一个辅助函数 `findBound(nums, target, isFirst)`，通过传入一个布尔类型的标志位 `isFirst` 来决定是找左边界还是右边界，从而让代码更加优雅、避免冗余。

### 复杂度分析
- **时间复杂度**：$O(\log n)$。我们执行了两次二分查找，每次的时间复杂度为 $O(\log n)$，总计 $2 \times O(\log n) = O(\log n)$，完美符合题目要求。
- **空间复杂度**：$O(1)$。只使用了常数级别的指针变量（`left`, `right`, `mid` 等），没有使用额外的集合空间。

## Java 实现

```java
class Solution {
    
    /**
     * 主方法：寻找目标值在数组中的第一个和最后一个位置
     */
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        
        // 边界情况处理：如果数组为空，直接返回 [-1, -1]
        if (nums == null || nums.length == 0) {
            return result;
        }

        // 第一次二分查找：寻找左边界（第一个位置）
        result[0] = findBound(nums, target, true);
        
        // 剪枝优化：如果连第一个位置都没找到，说明数组中不存在该目标值，直接返回即可
        if (result[0] == -1) {
            return result;
        }
        
        // 第二次二分查找：寻找右边界（最后一个位置）
        result[1] = findBound(nums, target, false);

        return result;
    }

    /**
     * 辅助方法：二分查找边界
     * @param nums 待查找的排序数组
     * @param target 目标值
     * @param isFirst 标志位：为 true 时寻找第一个位置（左边界），为 false 时寻找最后一个位置（右边界）
     * @return 目标值的位置，如果未找到返回 -1
     */
    private int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0;
        int right = nums.length - 1;
        int bound = -1; // 记录最近一次找到 target 的位置

        while (left <= right) {
            // 防溢出的写法，等同于 (left + right) / 2
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                // 找到目标值，先记录下位置
                bound = mid;
                // 根据需求决定下一步的搜索方向
                if (isFirst) {
                    // 如果找第一个位置，说明我们要逼近左边界，因此缩小右边界
                    right = mid - 1;
                } else {
                    // 如果找最后一个位置，说明我们要逼近右边界，因此扩大左边界
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                // 当前值小于目标值，目标值一定在右半区间
                left = mid + 1;
            } else {
                // 当前值大于目标值，目标值一定在左半区间
                right = mid - 1;
            }
        }
        
        return bound;
    }
}