好的，我将为您讲解一个新的算法题目。这次我们选择 LeetCode 第 34 题「在排序数组中查找元素的第一个和最后一个位置」。

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

题目描述

给定一个按照升序排列的整数数组 nums 和一个目标值 target，要求找出 target 在数组中的开始位置和结束位置。如果 target 不存在于数组中，返回 [-1, -1]。

示例 1：

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

示例 2：

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

解题思路

这道题的核心是高效地找到 target 的第一个和最后一个位置。由于数组是排序的，我们可以利用二分查找来优化时间复杂度。

步骤详解

1. 理解问题

我们需要找到 target 的“左边界”和“右边界”：

• 左边界：target 第一次出现的位置。
• 右边界：target 最后一次出现的位置。

2. 二分查找左边界

左边界是第一个等于 target 的位置。我们可以修改二分查找：

• 如果 nums[mid] == target，继续向左搜索（right = mid - 1）。
• 如果 nums[mid] < target，说明目标在右侧（left = mid + 1）。
• 如果 nums[mid] > target，说明目标在左侧（right = mid - 1）。

代码实现：

def find_left_bound(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left if left < len(nums) and nums[left] == target else -1

3. 二分查找右边界

右边界是最后一个等于 target 的位置。同样修改二分查找：

• 如果 nums[mid] == target，继续向右搜索（left = mid + 1）。
• 如果 nums[mid] < target，说明目标在右侧（left = mid + 1）。
• 如果 nums[mid] > target，说明目标在左侧（right = mid - 1）。

代码实现：

def find_right_bound(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    return right if right >= 0 and nums[right] == target else -1

4. 合并结果

调用上述两个函数，合并结果：

def searchRange(nums, target):
    left = find_left_bound(nums, target)
    right = find_right_bound(nums, target)
    return [left, right]

5. 边界情况处理

• 如果 nums 为空，直接返回 [-1, -1]。
• 如果 target 不存在于 nums 中，返回 [-1, -1]。

时间复杂度

• 两次二分查找，时间复杂度为 O(log n)。

完整代码

def searchRange(nums, target):
    def find_left_bound(nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left if left < len(nums) and nums[left] == target else -1

    def find_right_bound(nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right if right >= 0 and nums[right] == target else -1

    left = find_left_bound(nums, target)
    right = find_right_bound(nums, target)
    return [left, right]

示例验证

以 nums = [5,7,7,8,8,10], target = 8 为例：

1. 左边界：find_left_bound 返回 3（第一个 8 的位置）。
2. 右边界：find_right_bound 返回 4（最后一个 8 的位置）。
3. 最终结果：[3, 4]。

希望这个讲解能帮助您理解如何在排序数组中高效查找元素的边界！如果有疑问，欢迎继续提问。