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.
Time and Space Complexity:
- Time Complexity: O(n) in the worst case.
- Space Complexity: O(1).
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:
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.
Time and Space Complexity:
- Time Complexity: O(log n) in the worst case.
- Space Complexity: O(1).
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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.
FAQs
Using a modified binary search is the most efficient way, with O(log n) time complexity. It continues searching right even after finding the target to ensure the last index is returned.
A standard binary search stops at the first found match. To get the last occurrence, we must continue searching the right half even after finding the target.
If the target is not found, the function should return -1 or None, indicating the element doesn’t exist in the array.
No, binary search only works efficiently on sorted arrays. For unsorted arrays, you must use linear search, which takes O(n) time.
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
