418. Find Index of Target in Sorted Array

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

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

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

Examples

Input: [2,4,4,6,8,8,10], 4
Output: 1
Explanation: 4 first appears at index 1. Binary search finds left-most occurrence.

Input: [1,2,3,4,5], 6
Output: -1
Explanation: 6 not in array. Returns -1.

Input: [3,3,3,3,3], 3
Output: 0
Explanation: All elements are 3. First occurrence is at index 0.

Constraints

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• nums is sorted in non-decreasing order
• -10^9 <= target <= 10^9

Asked by