Last Occurrence in a Sorted Array
Introduction
In data analysis and computer science, locating the last occurrence in a sorted array of a specific element in a sorted array is a common task. Whether you’re working with numerical data, textual data, or any other type of dataset, knowing how to efficiently find the last occurrence can be invaluable. This page explores different methods and algorithms for finding the element that occurs last in the given set of array.
What is Last Occurrence in a Sorted Array?
“Last occurrence in a sorted array” refers to the position or index of the final instance of a specific element within an array that has been sorted in ascending order. It involves finding the last occurrence of a particular value in the sorted array.
For example :
- If you have a sorted array : [0, 1, 1, 2, 3, 4, 4, 4, 5, 7]
and you want to find the last occurrence of the element ‘4’, the “last occurrence in a sorted array” in this context would be to determine that the element ‘4’ appears at the index position of ‘7’ (assuming a zero-based index).
Two Approach for Last Occurrence in a Sorted Array
There are mainly two approaches for finding out the last occurrence:
Linear Search Approach (Brute Force Approach)
Binary Search Approach
Linear Search Approach
Linear search involves iterating through the array sequentially, starting from the beginning and proceeding to the end. Here’s how you can use linear search to find the last occurrence of an element in a sorted array:
Example :
def last_occurrence_linear(arr, target):
last_index = -1
for i in range(len(arr)):
if arr[i] == target:
last_index = i
return last_index
# Example usage:
sorted_array = [1, 2, 2, 3, 4, 4, 4, 5, 6, 7]
element_to_find = 4
index = last_occurrence_linear(sorted_array, element_to_find)
if index != -1:
print("The last occurrence of", element_to_find, "is at index", index)
else:
print(element_to_find, "was not found in the array.")
Output :
The last occurrence of 4 is at index 6.
Binary Search Approach
Binary search is a more efficient method for finding the last occurrence of an element in a sorted array. It narrows down the search space by dividing the array in half with each comparison. Here’s how you can use binary search for this task:
Example :
def last_occurrence_binary(arr, target):
left, right = 0, len(arr) - 1
last_index = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
last_index = mid
left = mid + 1 # Search the right subarray for the last occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return last_index
# Example usage:
sorted_array = [1, 2, 2, 3, 4, 4, 4, 5, 6, 7]
element_to_find = 4
index = last_occurrence_binary(sorted_array, element_to_find)
if index != -1:
print("The last occurrence of", element_to_find, "is at index", index)
else:
print(element_to_find, "was not found in the array.")
Output :
The last occurrence of 4 is at index 6.
Complexity Analysis
Linear Search:
- Time Complexity: O(n) in the worst case.
- Space Complexity: O(1).
Binary Search:
- Time Complexity: O(log n) in the worst case.
- Space Complexity: O(1).
Points to Remember
To wrap it up:
In this comprehensive guide, we’ve explored the critical concept of finding the last occurrence in a sorted array. Whether you’re a programmer, data analyst, or involved in various domains requiring efficient data retrieval, understanding this task is essential.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
Why would I need to find the last occurrence in a sorted array?
This operation is often useful in scenarios where you want to know the index of the rightmost occurrence of a particular element, such as when you’re searching for a specific value in a sorted list of data.
Question 2.
What’s the difference between finding the first occurrence and the last occurrence in a sorted array?
When finding the first occurrence, you stop the binary search as soon as you find the target element. To find the last occurrence, you continue the search even after finding the target element and keep updating the result until the search range is exhausted.
Question 3.
What happens if the element I’m searching for is not in the sorted array?
If the element is not in the sorted array, the algorithm will return -1 as it’s initialized as the default result. This indicates that the target element was not found.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
