Count Occurrences of Element in Sorted Array in DSA Go - Deep Dive

Overview - Count Occurrences of Element in Sorted Array

What is it?

Counting occurrences of an element in a sorted array means finding how many times that element appears in the list. Since the array is sorted, all instances of the element are grouped together. This makes it easier and faster to count them than in an unsorted array. The goal is to find the count efficiently without checking every element one by one.

Why it matters

Without this method, counting occurrences would require checking every element, which is slow for large arrays. Efficient counting helps in searching, data analysis, and many algorithms where frequency matters. It saves time and computing power, making programs faster and more responsive.

Where it fits

Before this, learners should understand arrays and basic searching methods like linear and binary search. After this, they can learn about frequency counting in unsorted arrays, hash maps, or advanced searching algorithms like interpolation search.

Mental Model

Core Idea

In a sorted array, all occurrences of an element are next to each other, so finding the first and last position of that element lets you count how many times it appears.

Think of it like...

Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title you have, you find where the first copy starts and where the last copy ends, then count all books in between.

Sorted Array: [1, 2, 2, 2, 3, 4, 5]
Element to count: 2
Positions: First occurrence at index 1, last occurrence at index 3
Count = last - first + 1 = 3 - 1 + 1 = 3

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why elements are grouped.

A sorted array is a list where elements are arranged in increasing order. For example, [1, 2, 2, 3, 4]. Because of sorting, all equal elements appear together. This grouping is key to counting occurrences efficiently.

Result

You know that if you find one occurrence of an element, others are right next to it.

Understanding sorting helps you realize why counting occurrences can be done faster than checking every element.

2

Foundation

Basic Linear Counting Method

Concept: Count occurrences by checking each element one by one.

Start from the beginning of the array and check each element. Increase a counter when you find the target element. Stop when elements are different or array ends. This works but can be slow for large arrays.

Result

For array [1, 2, 2, 2, 3], counting 2 gives 3 after checking elements at indexes 1, 2, and 3.

This method is simple but inefficient for big arrays because it checks many elements unnecessarily.

3

Intermediate

Using Binary Search to Find First Occurrence

🤔Before reading on: do you think binary search can find the first occurrence directly or just any occurrence? Commit to your answer.

Concept: Modify binary search to find the first position where the element appears.

Binary search splits the array in half repeatedly. To find the first occurrence, when you find the element, continue searching the left half to see if it appears earlier. Stop when you can't find it earlier.

Result

For [1, 2, 2, 2, 3], first occurrence of 2 is at index 1.

Knowing how to tweak binary search to find boundaries is key to efficient counting.

4

Intermediate

Using Binary Search to Find Last Occurrence

🤔Before reading on: do you think finding the last occurrence is similar to finding the first? Commit to your answer.

Concept: Modify binary search to find the last position where the element appears.

When binary search finds the element, continue searching the right half to find if it appears later. Stop when no later occurrence is found.

Result

For [1, 2, 2, 2, 3], last occurrence of 2 is at index 3.

Finding both first and last occurrences lets you calculate count without scanning all elements.

5

Intermediate

Calculating Count from Boundaries

Concept: Use first and last occurrence indexes to find total count.

Count = last occurrence index - first occurrence index + 1. If element not found, count is zero.

Result

For 2 in [1, 2, 2, 2, 3], count = 3 - 1 + 1 = 3.

This formula leverages the sorted property to count quickly and accurately.

6

Advanced

Efficient Go Implementation with Binary Search

🤔Before reading on: do you think a single binary search can find count or do we need two? Commit to your answer.

Concept: Implement two binary searches in Go to find first and last occurrences and calculate count.

package main import "fmt" func firstOccurrence(arr []int, target int) int { low, high := 0, len(arr)-1 result := -1 for low <= high { mid := low + (high-low)/2 if arr[mid] == target { result = mid high = mid - 1 // search left side } else if arr[mid] < target { low = mid + 1 } else { high = mid - 1 } } return result } func lastOccurrence(arr []int, target int) int { low, high := 0, len(arr)-1 result := -1 for low <= high { mid := low + (high-low)/2 if arr[mid] == target { result = mid low = mid + 1 // search right side } else if arr[mid] < target { low = mid + 1 } else { high = mid - 1 } } return result } func countOccurrences(arr []int, target int) int { first := firstOccurrence(arr, target) if first == -1 { return 0 } last := lastOccurrence(arr, target) return last - first + 1 } func main() { arr := []int{1, 2, 2, 2, 3, 4, 5} target := 2 count := countOccurrences(arr, target) fmt.Printf("Count of %d in array: %d\n", target, count) }

Result

Count of 2 in array: 3

Implementing binary search twice is the most efficient way to count occurrences in a sorted array.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the method works if the element is not present or array is empty? Commit to your answer.

Concept: Consider cases where element is missing, array is empty, or all elements are the same.

If element not found, firstOccurrence returns -1, so count is zero. For empty arrays, searches return -1 immediately. If all elements are the same and equal to target, first is 0 and last is len(arr)-1, count is full length. This method always runs in O(log n) time.

Result

Correct counts for all edge cases without extra checks or loops.

Understanding edge cases ensures robust code that never crashes or gives wrong counts.

Under the Hood

Binary search works by repeatedly dividing the search space in half. For first occurrence, when the target is found, the search continues to the left half to find an earlier occurrence. For last occurrence, it continues to the right half. This ensures the exact boundaries are found efficiently. The count is then the difference between these boundaries plus one.

Why designed this way?

This approach was designed to leverage the sorted property of arrays, which groups equal elements together. Linear search is simple but slow. Binary search reduces time complexity from O(n) to O(log n). The two separate searches for first and last occurrence ensure precise boundary detection, which a single search cannot guarantee.

Array indexes: 0  1  2  3  4  5  6
Array values:  1  2  2  2  3  4  5

Binary Search for First Occurrence:
Start: low=0, high=6
Find 2 at mid=3
Move high to mid-1=2 to find earlier 2
Find 2 at mid=1
Move high to mid-1=0
No earlier 2 found, first occurrence=1

Binary Search for Last Occurrence:
Start: low=0, high=6
Find 2 at mid=3
Move low to mid+1=4 to find later 2
No 2 found at mid=5
Last occurrence=3

Count = 3 - 1 + 1 = 3

Myth Busters - 3 Common Misconceptions

Quick: Does binary search always find the first occurrence of an element? Commit yes or no.

Common Belief: Binary search always returns the first occurrence of the element.

Reality: Standard binary search returns any occurrence, not necessarily the first. You must modify it to find the first occurrence.

Why it matters: Using standard binary search can lead to incorrect counts if you assume the found index is the first occurrence.

Quick: If the element is not in the array, does the count return -1 or 0? Commit your answer.

Common Belief: If the element is not found, the count should be -1 or an error.

Reality: The count should be 0 because the element does not appear in the array.

Why it matters: Returning -1 or error can cause bugs or crashes in programs expecting a count.

Quick: Is linear search always slower than binary search for counting occurrences? Commit yes or no.

Common Belief: Linear search is always slower than binary search for counting occurrences in sorted arrays.

Reality: Linear search can be faster if the element occurs many times at the start or end, but generally binary search is faster for large arrays.

Why it matters: Choosing binary search blindly without considering data distribution can lead to unnecessary complexity.

Expert Zone

1

Binary search for boundaries requires careful handling of mid calculation to avoid infinite loops or missing edge cases.

2

When elements are repeated many times, binary search reduces time drastically compared to linear scanning, especially for large arrays.

3

In some languages or systems, built-in functions like lower_bound and upper_bound implement these searches efficiently and should be preferred.

When NOT to use

If the array is unsorted, this method fails. Use hash maps or frequency counters instead. For very small arrays, linear search might be simpler and faster. If data is streaming or changing frequently, consider balanced trees or other dynamic data structures.

Production Patterns

In databases and search engines, counting occurrences quickly helps in query optimization. In analytics, frequency counts are used for histograms and statistics. This method is a building block for more complex algorithms like finding modes or duplicates.

Connections

Binary Search

Builds-on

Understanding binary search deeply is essential because counting occurrences in sorted arrays is a direct application of finding boundaries using binary search.

Hash Maps

Alternative approach

Hash maps count occurrences efficiently in unsorted arrays, showing how different data structures solve similar problems under different conditions.

Signal Processing

Pattern detection analogy

Counting occurrences in sorted arrays is like detecting repeated signals in a time series, where grouping and boundaries matter for analysis.

Common Pitfalls

#1 Assuming binary search returns the first occurrence directly.

Wrong approach:

func firstOccurrence(arr []int, target int) int {
low, high := 0, len(arr)-1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == target {
return mid // returns any occurrence, not first
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}

Correct approach:

func firstOccurrence(arr []int, target int) int {
low, high := 0, len(arr)-1
result := -1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == target {
result = mid
high = mid - 1 // continue searching left
} else if arr[mid] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return result
}

Root cause:

Misunderstanding that standard binary search stops at any found occurrence instead of searching for boundaries.

#2 Not handling the case when element is not found, leading to wrong count.

Wrong approach:

func countOccurrences(arr []int, target int) int {
first := firstOccurrence(arr, target)
last := lastOccurrence(arr, target)
return last - first + 1 // no check if first == -1
}

Correct approach:

func countOccurrences(arr []int, target int) int {
first := firstOccurrence(arr, target)
if first == -1 {
return 0
}
last := lastOccurrence(arr, target)
return last - first + 1
}

Root cause:

Forgetting to check if the element exists before calculating count.

#3 Using linear search for large sorted arrays unnecessarily.

Wrong approach:

func countOccurrences(arr []int, target int) int {
count := 0
for _, val := range arr {
if val == target {
count++
}
}
return count
}

Correct approach:

Use binary search based method shown earlier for O(log n) performance.

Root cause:

Not leveraging the sorted property to optimize counting.

Key Takeaways

Counting occurrences in a sorted array is efficient because all equal elements are grouped together.

Binary search can be modified to find the first and last positions of an element, enabling quick counting.

Always check if the element exists before calculating the count to avoid errors.

This method runs in O(log n) time, much faster than linear search for large arrays.

Understanding edge cases and careful implementation ensures robust and correct counting.