循环不变量的应用：实现二分查找的变体

题目描述：给定一个已排序的整数数组和一个目标值，数组可能包含重复元素。请实现一个算法，在O(log n)时间复杂度内找到目标值在数组中第一次出现的位置（左边界）。如果目标值不存在于数组中，则返回-1。

解题步骤：

1. 理解问题核心

   • 这不是简单的二分查找，需要找到第一个等于目标值的索引
   • 示例：数组[1,2,3,3,3,4,5]，目标值3，应返回索引2（第一个3的位置）

2. 标准二分查找的局限性

   • 普通二分找到的是任意一个目标值，不保证是第一个
   • 需要修改二分逻辑来处理重复元素的情况

3. 循环不变量的定义

   • 定义搜索区间为[left, right]，其中left=0，right=数组长度-1
   • 循环不变量：目标值的第一次出现位置一定在[left, right]区间内
   • 初始化时，这个区间包含整个数组，满足不变量

4. 修改二分判断逻辑

   • 当nums[mid] == target时，不立即返回
   • 因为可能前面还有相同的目标值，需要继续向左搜索
   • 此时将右边界移动到mid-1，缩小搜索范围

5. 具体实现步骤

   def find_first_occurrence(nums, target):
       left, right = 0, len(nums) - 1
       result = -1  # 记录最终结果
   
       while left <= right:
           mid = left + (right - left) // 2  # 防止整数溢出
   
           if nums[mid] == target:
               result = mid    # 记录当前位置
               right = mid - 1 # 继续向左搜索
           elif nums[mid] < target:
               left = mid + 1  # 目标在右侧
           else:
               right = mid - 1 # 目标在左侧
   
       return result
   

6. 算法正确性分析

   • 每次循环都保持"目标值的第一次出现位置在[left, right]内"的不变量
   • 当nums[mid] == target时，记录当前位置并继续向左搜索
   • 最终left > right时，result记录的就是最左边的目标值位置

7. 边界情况处理

   • 空数组：直接返回-1
   • 目标值不存在：result保持初始值-1
   • 单个元素数组：正常处理

8. 时间复杂度分析

   • 每次循环将搜索范围减半：O(log n)
   • 空间复杂度：O(1)，只使用有限变量

这个算法展示了如何通过修改二分查找的终止条件来处理边界查找问题，是二分查找的重要变体。