Problem
Given a sorted integer array nums and an integer target, return the first occurrence of the target. If the target does not exist in the array, return -1.The array may contain duplicate values.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,2,2,3,4]
target = 2 Output
1 Solution
This solution uses Binary Search. When the target is found, its index is stored as a possible answer, but the search continues toward the left to check whether an earlier occurrence exists.If the middle value is greater than or equal to the target, the search continues in the left half. Otherwise, it continues in the right half.
By continuing the search after finding the target, the algorithm ensures that the first occurrence is returned.
public int findFirstOccurrence(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
Complexity
Each iteration eliminates half of the remaining search space, resulting in a time complexity ofO(log n). The algorithm uses only a few variables, so the extra space complexity is O(1).