easyBinary SearchPattern: Binary Search
Find First Occurrence in Sorted Array Solution
Problem Statement
Given a strictly increasing array of integers `nums` and an integer `target`, return the index of the first occurrence of `target` in `nums`. If `target` is not present in the array, return -1. You must write an algorithm with O(log n) runtime complexity.
Examples
Example 1:
Input:{"nums":[2,5,5,5,6,6,8,9,9,9],"target":5}
Output:1
Explanation: The target value 5 first appears at index 1.
Example 2:
Input:{"nums":[1,3,4,7,10],"target":6}
Output:-1
Explanation: The target value 6 does not appear in the array.
Example 3:
Input:{"nums":[10,20,30,40,50],"target":10}
Output:0
Explanation: The target value 10 first appears at index 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in strictly increasing order.
- -10^9 <= target <= 10^9
Time: O(log n) Space: O(1)
Use a modified binary search. When the middle element equals the target, record the index and continue searching in the left half to find an earlier occurrence. If the middle element is less than the target, search the right half. If it's greater, search the left half. This ensures finding the first occurrence in O(log n) time.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_first_occurrence(nums, target):
low = 0
high = len(nums) - 1
first_occurrence = -1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
first_occurrence = mid
high = mid - 1 # Try to find an earlier occurrence in the left half
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return first_occurrence