LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

题目要求在非递减顺序排列的整数数组 nums 中查找目标值 target 的第一个和最后一个位置。如果 target 不存在于数组中，则返回 [-1, -1]。并且要求算法的时间复杂度为 O(log n)，这提示我们需要使用二分查找。

提供的代码尝试通过两次二分查找分别找到 target 的起始位置和结束位置。然而，代码中存在一些逻辑问题，可能导致在某些情况下无法正确返回结果。以下是代码的主要问题：

1. 初始检查：代码首先检查 nums 是否为空，以及 target 是否在 nums 的最小值和最大值之外。这些检查是合理的，但可以进一步优化。
2. 寻找起始位置 (resleft)：

   使用二分查找来定位 target 的起始位置。

   当 nums[left] == target 时，直接设置 resleft = left 并跳出循环，这可能导致遗漏更早的起始位置。

   循环结束后，如果没有找到 resleft，再检查 nums[left] 和 nums[right] 是否等于 target。

3. 寻找结束位置 (resright)：

   类似地，使用二分查找来定位 target 的结束位置。

   当 nums[right] == target 时，直接设置 resright = right 并跳出循环，这可能导致遗漏更晚的结束位置。

   循环结束后，如果没有找到 resright，再检查 nums[left] 和 nums[right] 是否等于 target。

4. 返回值：如果 resleft 或 resright 未找到，则返回 [-1, -1]。

1. 逻辑问题：

   在寻找起始位置时，如果 nums[left] == target，直接设置 resleft = left 并跳出循环，可能会忽略更早的起始位置（例如，nums[left] 和 nums[left + 1] 都等于 target）。

   类似地，在寻找结束位置时，如果 nums[right] == target，直接设置 resright = right 并跳出循环，可能会忽略更晚的结束位置。

2. 边界条件：

   当 nums 中所有元素都等于 target 时，代码可能无法正确处理。

   当 nums 中只有一个元素等于 target 时，代码可能无法正确处理。

3. 优化：

   可以分别实现两个辅助函数 find_left 和 find_right，分别用于查找起始位置和结束位置。

   在 find_left 中，当 nums[mid] >= target 时，继续向左搜索；否则向右搜索。

   在 find_right 中，当 nums[mid] <= target 时，继续向右搜索；否则向左搜索。

1. find_left 函数：

   使用二分查找定位 target 的起始位置。

   当 nums[mid] >= target 时，继续向左搜索（right = mid - 1）；否则向右搜索（left = mid + 1）。

   如果 nums[mid] == target，更新 res 为 mid。

   最终返回 res，即 target 的起始位置或 -1（如果未找到）。

2. find_right 函数：

   使用二分查找定位 target 的结束位置。

   当 nums[mid] <= target 时，继续向右搜索（left = mid + 1）；否则向左搜索（right = mid - 1）。

   如果 nums[mid] == target，更新 res 为 mid。

   最终返回 res，即 target 的结束位置或 -1（如果未找到）。

3. 主函数 searchRange：

   首先检查 nums 是否为空，如果是，直接返回 [-1, -1]。

   调用 find_left 查找起始位置，如果未找到（left_pos == -1），直接返回 [-1, -1]。

   调用 find_right 查找结束位置。

   返回 [left_pos, right_pos]。

1. 示例 1：

   输入：nums = [5,7,7,8,8,10], target = 8

   find_left 返回 3，find_right 返回 4。

   输出：[3, 4]。

2. 示例 2：

   输入：nums = [5,7,7,8,8,10], target = 6

   find_left 返回 -1。

   输出：[-1, -1]。

3. 示例 3：

   输入：nums = [], target = 0

   直接返回 [-1, -1]。

• 时间复杂度：O(log n)，因为使用了两次二分查找。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

改进后的代码通过两次独立的二分查找分别定位 target 的起始和结束位置，确保了算法的高效性和正确性。逻辑清晰，边界条件处理完善，能够正确处理所有可能的输入情况。