Find First and Last Position of Element in Sorted Array

When dealing with a sorted array, one of the common problems that often arises is determining the first and last position of a specific element. This task can be solved efficiently using binary search, a well-known search algorithm. In this article, we will explore the algorithm for finding the first occurrence and last occurrence of an element, as well as the algorithm complexity.

Understand the Problem

Given a sorted array, you are tasked with finding the first position and last position of a specific element. This requires checking the array indices to determine where the element first and last appears. While brute force solutions involve scanning the entire array, we can take advantage of the sorted nature of the array to solve the problem in logarithmic time, making the solution efficient.

Efficient Approach with Binary Search

Since the array is sorted, binary search is the optimal way to find the first occurrence and last occurrence of the element. Binary search helps us cut the search space in half at each step, leading to an efficient lookup in O(log n) time.

Binary Search for First Occurrence

To find the first occurrence of an element, you need to modify the typical binary search. Instead of stopping when the element is found, you continue to search the left half of the array to ensure that you get the first position. Here's how the algorithm works:

1. Perform binary search to find the middle element.
2. If the middle element is the target, continue searching in the left half to check if the target appears earlier.
3. If the middle element is greater than the target, move to the left half.
4. If the middle element is less than the target, move to the right half.

Code for First Occurrence

1
2
3
4
5
6
7
8
9
10
11
12
13
def findFirstPosition(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # Search on the left side for the first occurrence
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Binary Search for Last Occurrence

To find the last occurrence of the element, the approach is quite similar. You modify the binary search to continue searching the right half if the target is found. Here's how you can adapt the algorithm:

• Perform binary search to find the middle element.
• If the middle element is the target, continue searching in the right half to ensure that you get the last position.
• If the middle element is greater than the target, move to the left half.
• If the middle element is less than the target, move to the right half.

Code for Last Occurrence

1
2
3
4
5
6
7
8
9
10
11
12
13
def findLastPosition(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            result = mid
            left = mid + 1  # Search on the right side for the last occurrence
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Combining Both Searches

You can combine both the searches for first and last position into a single function that will return both positions in one pass. This method improves efficiency by minimizing the number of searches. Here's how you can implement it:

1
2
3
4
def findFirstAndLastPosition(nums, target):
    first = findFirstPosition(nums, target)
    last = findLastPosition(nums, target)
    return [first, last]  # Return both first and last positions

Algorithm Complexity

The time complexity for both the first and last occurrence searches is O(log n) because we are using binary search. Each search cuts the search space in half, leading to logarithmic time complexity.

• Time Complexity: O(log n) for both the first and last position searches.
• Space Complexity: O(1), as the solution uses only a constant amount of extra space.

Edge Cases

When implementing the solution, it's essential to handle various edge cases:

• If the element is not present in the sorted array, both the first and last positions will return -1.
• If the array contains only one element, the search will either return the position of that element or -1 if it's not the target.
• If there are duplicate elements in the array, the solution will correctly return the first and last positions of the target.

Conclusion

In conclusion, finding the first and last position of an element in a sorted array can be efficiently done using a binary search approach. The search algorithm provides an efficient lookup and reduces the problem to logarithmic time complexity. By leveraging the sorted nature of the array, we can optimize the solution and ensure that the task is completed with minimal computational resources.