Why Count Occurrences of Element in Sorted Array in DSA Javascript?

The Big Idea

What if you could count repeated items in a huge sorted list in just a few quick steps?

The Scenario

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

The Problem

Manually scanning through the entire list to count occurrences is slow and tiring. It wastes time especially when the list is very long. Also, it's easy to make mistakes by missing some numbers or counting wrong.

The Solution

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

Before vs After

✗ Before

let count = 0;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === target) count++;
}

✓ After

function countOccurrences(arr, target) {
  const first = findFirst(arr, target);
  const last = findLast(arr, target);
  return first === -1 ? 0 : last - first + 1;
}

What It Enables

This lets you quickly find how many times a number appears in a sorted list, even if the list is huge.

Real Life Example

When searching for how many times a word appears in a sorted dictionary or how many customers bought a specific product sorted by product ID, this method saves time and effort.

Key Takeaways

Manually counting is slow and error-prone.

Using the sorted order helps find counts quickly.

This method works well even for very large lists.