First Occurrence of Target in Sorted Array
Problem Statement
Given a sorted array nums with duplicates and a target value, return the index of the first occurrence of the target. If the target is not found, return -1.
Example Test Cases
- Input:
nums = [1, 2, 3, 4, 4, 5], target = 4
Output: 3
- Input:
nums = [1, 1, 2, 3, 5, 6], target = 4
Output: -1
Approaches
Brute Force Approach
-
Idea: Traverse the array and return the index of the first occurrence of the target.
-
Steps:
- Iterate through each element in the array.
- If the current element is equal to the target, return its index.
- If no element matches, return
-1.
-
Time Complexity: O(n) where n is the length of the array.
-
Space Complexity: O(1) as it uses constant extra space.
-
Example Code:
- Dry Run:
Input:
nums = [1, 2, 3, 4, 4, 5], target = 4
- Iterate through the array: at index
3, nums[3] == 4
- Return
3.
Efficient Approach (Binary Search)
-
Idea: Use binary search to find the first occurrence of the target in the sorted array.
-
Steps:
- Initialize
low to 0 and high to n - 1.
- Perform binary search:
- If
nums[mid] equals the target and is the first occurrence (either mid == 0 or nums[mid - 1] < target), return mid.
- If
nums[mid] is greater than or equal to the target, move high to mid - 1 to find the first occurrence.
- Otherwise, move
low to mid + 1.
- If the target is not found, return
-1.
-
Time Complexity: O(log n) where n is the length of the array.
-
Space Complexity: O(1) as it uses constant extra space.
-
Example Code:
- Dry Run:
Input:
nums = [1, 2, 3, 4, 4, 5], target = 4
low = 0, high = 5, mid = 2 → nums[2] < 4, move low = 3low = 3, mid = 4, nums[4] == 4, but nums[3] == 4, move high = 3low = 3, high = 3, nums[3] == 4, return 3.
Complexity Analysis
Brute Force Approach
- Time Complexity:
O(n)
- Space Complexity:
O(1)
Efficient Approach
- Time Complexity:
O(log n)
- Space Complexity:
O(1)
Conclusion
The brute force approach is straightforward but inefficient for large arrays. The binary search approach efficiently finds the first occurrence in logarithmic time.