6. Find First Occurrence

Origin：Find First Occurrence

Given a sorted array of integers that may contain duplicates, return the index of the first occurrence of a target value or -1 if not found.

Example

Input:

nums = [1, 2, 3, 4, 5]
target = 3
Output:

2

Explanation:

 
We perform binary search on [1,2,3,4,5].
 
low=0, high=4 → mid=2 → nums[2]=3 equals target. Record result=2, then search left half.
 
Update high=mid-1=1. Now low=0, high=1 → mid=0 → nums[0]=1 < target, so move low to mid+1=1.
 
low=1, high=1 → mid=1 → nums[1]=2 < target, so move low to mid+1=2.
 
Now low(2)>high(1), terminate. The first occurrence found is at index 2.

Input Format

The input consists of two lines.

First line: two space-separated integers n and target, where 0 <= n <= 1000 and -10^9 <= target <= 10

Second line: n space-separated integers nums[i], each satisfying -10^9 <= nums[i] <= 10^9, and nums is sorted in non-decreasing order.

Edge cases include: n = 0 (empty array), all elements less than target, all elements greater than target, multiple duplicates of target, single-element array.

Constraints

0 <= nums.length <= 1000
 
-10^9 <= nums[i] <= 10^9 for all 0 <= i < nums.length
 
-10^9 <= target <= 10^9
 
For all 0 <= i < nums.length - 1, nums[i] <= nums[i+1] (array is non-decreasingly sorted)
 

Output Format

Output a single integer: the index (0-based) of the first occurrence of target in the array nums. If target does not exist in nums, output -1.

Sample Input 0

0
5

Sample Output 0

-1

Sample Input 1

1
3
3

Sample Output 1

0

Resolution

核心思路： 二分查找寻找左边界。普通二分找到目标值就直接返回，但此题要求第一个出现的位置，所以当命中目标时不能立即返回，而是收缩右边界继续在左侧搜索。

算法步骤：

1. 初始化 low = 0, high = n - 1, result = -1
2. while (low <= high) 循环：
   • 计算 mid = Math.floor((low + high) / 2)
   • 如果 nums[mid] === target：记录 result = mid，然后 high = mid - 1（继续在左半部分找更早的出现）
   • 如果 nums[mid] < target：low = mid + 1（目标在右侧）
   • 如果 nums[mid] > target：high = mid - 1（目标在左侧）
3. 返回 result

复杂度： 时间 O(log n)，空间 O(1)

参考实现：

function findFirstOccurrence(nums: number[], target: number): number {
    let low = 0;
    let high = nums.length - 1;
    let result = -1;
 
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) {
            result = mid;
            high = mid - 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
 
    return result;
}

我的解法

function findFirstOccurrence(nums: number[], target: number): number {
    // Write your code here
    if (!nums.length) return -1
    let low = 0;
    let high = nums.length - 1
 
    if (target < nums[0]) {
        return -1
    }
    if (target > nums[high]) {
        return -1
    }
 
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (nums[mid] === target) {
            while (mid > 0 && nums[mid - 1] === target) {
                mid--
            }
            return mid
        } else if (nums[mid] > target) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
 
    return -1
}

思路： 先用二分查找快速定位到任意一个等于 target 的位置，找到后不直接返回，而是从该位置向前线性扫描，直到找到第一个出现的 target。

复杂度：

• 时间复杂度：平均 O(log n)，最坏 O(n)。当数组中存在大量重复的 target 时（如 [3, 3, 3, 3, 3]），线性回退需要遍历这些元素。
• 空间复杂度：O(1)。