二分查找的变种问题（查找第一个/最后一个等于目标值的位置）

题目描述
给定一个非递减排序数组（可能有重复元素）和一个目标值，要求实现两个函数：

1. 查找第一个等于目标值的元素位置
2. 查找最后一个等于目标值的元素位置
   若目标值不存在，返回-1。要求时间复杂度为O(log n)。

解题思路
标准二分查找适用于无重复元素的数组，但遇到重复元素时需调整边界收缩策略。核心在于：

• 找到目标值后不立即返回，而是继续向一侧收缩边界，直到锁定第一个或最后一个目标值。

步骤详解

1. 查找第一个等于目标值的位置

• 初始化：左指针left=0，右指针right=n-1（n为数组长度）。
• 循环条件：while left <= right（确保搜索区间有效）。
• 中间位置：mid = left + (right - left) // 2（防溢出）。
• 关键逻辑：
  • 若nums[mid] < target，目标值在右侧，left = mid + 1。
  • 若nums[mid] > target，目标值在左侧，right = mid - 1。
  • 若nums[mid] == target，需判断是否为第一个：
    • 如果mid == 0（已到数组头）或nums[mid-1] != target（前一个元素不等于目标值），则mid是第一个目标值。
    • 否则，继续在左侧搜索（right = mid - 1）。
• 终止条件：若循环结束未找到，返回-1。

示例：
数组[1,2,2,2,3]，目标值2

• 第一轮：mid=2，nums[2]=2，但nums[1]=2，继续向左搜索（right=1）。
• 第二轮：mid=0+(1-0)//2=0，nums[0]=1<2，left=1。
• 第三轮：mid=1，nums[1]=2，且nums[0]=1≠2，找到第一个位置1。

2. 查找最后一个等于目标值的位置

• 初始化：同上。
• 关键逻辑：
  • 当nums[mid] == target时：
    • 如果mid == n-1（已到数组尾）或nums[mid+1] != target（后一个元素不等于目标值），则mid是最后一个目标值。
    • 否则，继续在右侧搜索（left = mid + 1）。
• 其他步骤与查找第一个位置对称。

示例：
数组[1,2,2,2,3]，目标值2

• 第一轮：mid=2，nums[2]=2，但nums[3]=2，继续向右搜索（left=3）。
• 第二轮：mid=3，nums[3]=2，且nums[4]=3≠2，找到最后一个位置3。

代码实现（Python）

def first_position(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:  # nums[mid] == target
            if mid == 0 or nums[mid - 1] != target:
                return mid
            else:
                right = mid - 1
    return -1

def last_position(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:  # nums[mid] == target
            if mid == len(nums) - 1 or nums[mid + 1] != target:
                return mid
            else:
                left = mid + 1
    return -1

总结

• 通过调整相等时的边界收缩方向，可解决重复元素的边界查找问题。
• 关键点：在找到目标值时，通过判断相邻元素进一步缩小范围，确保锁定第一个或最后一个位置。