420. Find the First Occurrence of Target

Given a sorted array nums (may contain duplicates) and an integer target, return the index of the first (leftmost) occurrence of target. Return -1 if target is not present. Solve in O(log n).

Input: A sorted non-decreasing integer array nums and integer target.

Output: Index of the first occurrence of target, or -1.

Examples

Input: [1,2,2,3,3,3,4], 3
Output: 3
Explanation: 3 appears at indices 3,4,5. First occurrence is index 3.

Input: [5,5,5,5,5], 5
Output: 0
Explanation: All elements are 5; first occurrence is index 0.

Input: [1,2,3,4,5], 9
Output: -1
Explanation: 9 is absent; return -1.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums sorted non-decreasing

Asked by