⬅ Previous Topic
First Occurrence in a Sorted ArrayNext Topic ⮕
Count Occurrences in Sorted Array⬅ Previous Topic
First Occurrence in a Sorted ArrayNext Topic ⮕
Count Occurrences in Sorted ArrayTopic Contents
Given a sorted array of integers and a target number key
, your task is to find the last occurrence (last index) of the key
in the array.
-1
.-1
.This problem is commonly solved using a modified version of binary search for better efficiency.
start = 0
, end = n - 1
, and res = -1
to store the result.start ≤ end
, calculate mid = start + (end - start) / 2
.arr[mid] == key
: update res = mid
and move start = mid + 1
to search towards the right.arr[mid] < key
: move start = mid + 1
.arr[mid] > key
: move end = mid - 1
.res
will contain the last occurrence index or -1 if not found.def last_occurrence(arr, key):
start, end = 0, len(arr) - 1
result = -1
while start <= end:
mid = start + (end - start) // 2
if arr[mid] == key:
result = mid # Record the index
start = mid + 1 # Move right to find a later occurrence
elif key < arr[mid]:
end = mid - 1
else:
start = mid + 1
return result
# Example usage
arr = [5, 10, 10, 10, 20, 20]
key = 10
print("Last Occurrence Index:", last_occurrence(arr, key))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | When the key is found at the first mid computation and no further checking is needed. |
Average Case | O(log n) | Each iteration halves the search space, leading to logarithmic performance. |
Worst Case | O(log n) | In the worst case, the search checks each level of the binary search tree until no more right occurrences are found. |
O(1)
Explanation: Only a fixed number of variables are used, with no extra memory required.
⬅ Previous Topic
First Occurrence in a Sorted ArrayNext Topic ⮕
Count Occurrences in Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.