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

The Big Idea

What if you could count items in a huge sorted list in just a few quick steps instead of checking one by one?

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 scanning through the entire list to count occurrences is slow and tiring. It's easy to lose track or make mistakes, especially if the list is very long. This wastes time and can cause errors.

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

count := 0
for i := 0; i < len(arr); i++ {
  if arr[i] == target {
    count++
  }
}

✓ After

start := findFirst(arr, target)
end := findLast(arr, target)
count := end - start + 1

What It Enables

This lets you count how many times an item appears in a sorted list quickly and accurately, even if the list is huge.

Real Life Example

In a library system, quickly finding how many copies of a book are available by searching a sorted list of book IDs helps manage inventory efficiently.

Key Takeaways

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

Using the sorted order lets us find occurrences quickly with special search methods.

This approach saves time and reduces mistakes in counting.