Why Count Occurrences of Element in Sorted Array in DSA C++?

The Big Idea

What if you could count repeated items in a huge sorted list in just a blink?

The Scenario

Imagine you have a long list of sorted numbers, like a phone book sorted by last name. You want to find out how many times a particular name appears. Doing this by checking each entry one by one would take a lot of time.

The Problem

Manually counting each occurrence means going through the entire list, even if the list is very long. This is slow and tiring, and you might lose track or make mistakes while counting.

The Solution

Using a smart method that takes advantage of the list being sorted, we can quickly find where the element starts and ends. This way, we count occurrences fast without checking every item.

Before vs After

✗ Before

int countOccurrences(int arr[], int size, int target) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) count++;
    }
    return count;
}

✓ After

int countOccurrences(int arr[], int size, int target) {
    int first = findFirst(arr, size, target);
    int last = findLast(arr, size, target);
    if (first == -1) return 0;
    return last - first + 1;
}

What It Enables

This method lets you count how many times an element appears in a sorted list very quickly, even if the list is huge.

Real Life Example

When searching a sorted database of customer IDs, you can instantly find how many times a specific ID appears without scanning the entire database.

Key Takeaways

Manual counting is slow and error-prone for large sorted lists.

Using the sorted order, we find the first and last positions of the element quickly.

This approach saves time and reduces mistakes.