Finding the First and Last Position of an Element in a Sorted Array: A Comprehensive Guide
Hello, guys! Today, we're going to tackle a common problem that often pops up in coding interviews: finding the first and last occurrence of a given element in a sorted array. This problem is not only interesting but also helps you understand how to apply binary search, a fundamental algorithm in computer science. So, buckle up and let's dive right in! Guys, explore more in Guides And Explainers and find first and last position of element in sorted array.
Understanding the Problem
Given a sorted array `nums` and a target value `target`, the problem is to find the first and last position of the target element in the array. If the target is not present, return `[-1, -1]`.
For example, consider the array `nums = [1, 2, 3, 3, 3, 4, 5]` and the target `target = 3`. The first occurrence of 3 is at index 2, and the last occurrence is at index 5. So, the output should be `[2, 5]`.
Naive Approach: Linear Search
The most straightforward approach is to use linear search. You can iterate through the array and keep track of the first and last occurrence of the target. However, this approach has a time complexity of O(n), which is not efficient for large arrays.
Here's a simple implementation in Python:
def searchRange(nums, target): first = -1 last = -1
for i in range(len(nums)): if nums[i] == target: if first == -1: first = i last = i
return [first, last]
Binary Search: The Efficient Way
Binary search can significantly improve the time complexity to O(log n). The idea is to perform two binary searches: one for finding the first occurrence and another for finding the last occurrence.
Finding the First Occurrence
To find the first occurrence, we can perform a left-closed, right-open binary search. This means we're looking for the largest index `i` such that `nums[i]
Here's the binary search algorithm for finding the first occurrence:
- 1. Initialize two pointers, `left` and `right`, to 0 and `n - 1` respectively, where `n` is the length of the array.
- 2. While `left
- 3. If `nums[left] == target`, return `left`. Otherwise, return `-1`.
Finding the Last Occurrence
To find the last occurrence, we can perform a left-open, right-closed binary search. This means we're looking for the smallest index `i` such that `nums[i] > target`. If no such index exists, then the target is not present in the array.
Here's the binary search algorithm for finding the last occurrence:
- 1. Initialize two pointers, `left` and `right`, to 0 and `n - 1` respectively, where `n` is the length of the array.
- 2. While `left = target`, set `right = mid - 1`. - Otherwise, set `left = mid + 1`.
- 3. If `nums[right] == target`, return `right`. Otherwise, return `-1`.
Putting It All Together
Now that we have the binary search algorithms for finding the first and last occurrence, we can combine them to solve the problem efficiently. Here's the final implementation in Python:
def searchRange(nums, target): def findFirst(nums, target): left, right = 0, len(nums) - 1 while left
def findLast(nums, target): left, right = 0, len(nums) - 1 while left target: right = mid - 1 else: left = mid + 1 if right >= 0 and nums[right] == target: return right else: return -1
return [findFirst(nums, target), findLast(nums, target)]
This implementation has a time complexity of O(log n) for each binary search, so the overall time complexity is O(log n). The space complexity is O(1), as we're only using a constant amount of extra space.
Conclusion
In this article, we've discussed the problem of finding the first and last position of an element in a sorted array. We started with a naive approach using linear search and then improved the time complexity using binary search. The final implementation is efficient and can handle large arrays with ease.
Guys, that's all for today! I hope this article helped you understand the problem and the various approaches to solve it. If you have any questions or suggestions, feel free to leave a comment below. Happy coding!
Word count: 1501