Find the Last Occurrence of an Element in a Sorted Array

Avnii Thakur
5h
2k
0
0

Article

💡 Introduction

When working with sorted arrays, searching for an element efficiently is one of the most common tasks. A typical Binary Search helps you find whether an element exists or not in O(log n) time.
But sometimes, you’re asked to find the first or last occurrence of a number — especially when duplicates exist.

For example,

Array = [2, 4, 4, 4, 5, 6]
Element = 4

Here,

The first occurrence of 4 is at index 1
The last occurrence of 4 is at index 3

Let’s learn how to find the last occurrence efficiently 🔍

🧠 Understanding the Problem

We are given:

A sorted array
A target element

We must find the index of the last occurrence of that element.
If the element does not exist, return -1.

⚙️ Approach 1. Linear Search (Brute Force)

The simplest (but slow) way is to:

Traverse the entire array from left to right.
Keep updating the index whenever the target matches.

Time Complexity: O(n)
Space Complexity: O(1)

✅ Works fine for small arrays, but not efficient for large ones.

🚀 Approach 2. Binary Search (Efficient Way)

Since the array is sorted, we can use Binary Search to reduce the time complexity to O(log n).

🧩 Logic

Use binary search to find the element.
When you find the target, don’t stop — move right to check if there are more occurrences.
Continue until no more matches are found on the right side.
Return the last found index.

💻 C++ Implementation

#include <iostream>using namespace std;

int findLastOccurrence(int arr[], int n, int target) {
    int start = 0, end = n - 1;
    int result = -1;

    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == target) {
            result = mid;       // update result
            start = mid + 1;    // move right to find last occurrence
        }
        else if (arr[mid] < target)
            start = mid + 1;
        else
            end = mid - 1;
    }

    return result;
}

int main() {
    int arr[] = {2, 4, 4, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    int index = findLastOccurrence(arr, n, target);

    if (index != -1)
        cout << "Last occurrence of " << target << " is at index " << index << endl;
    else
        cout << "Element not found" << endl;

    return 0;
}

🧾 Example Dry Run

Input:
arr = [2, 4, 4, 4, 5, 6], target = 4

Step	Start	End	Mid	arr[mid]	Action
1	0	5	2	4	Found → move right
2	3	5	4	5	Too high → move left
3	3	3	3	4	Found → move right

✅ Last occurrence = index 3

⏱️ Time & Space Complexity

Type	Complexity
Time	O(log n)
Space	O(1)

🧩 Key Takeaways

Binary search can be modified to find the first or last occurrence of an element.
Always continue searching in the right half after finding the element to locate its last position.
Efficient for large sorted arrays.

🧠 Bonus Tip

You can easily modify this same logic to find the first occurrence by moving the pointer to the left instead of the right.

🏁 Conclusion

Finding the last occurrence of an element in a sorted array is a classic example of how simple modifications to binary search logic can make your program both fast and efficient.

Practice this problem and try writing it in different languages like C++, Java, and Python to solidify your understanding 💪