Count Occurrences of Element in Sorted Array in DSA Go

Mental Model

In a sorted list, all copies of the same number are next to each other. We find where the number starts and ends to count how many times it appears.

Analogy: Imagine a row of identical books on a shelf. To count how many copies of one title there are, you find the first copy and the last copy, then count all books in between.

Array: [1, 2, 2, 2, 3, 4, 5]
          ↑        ↑
       first     last
       occurrence occurrence

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], element: 2

Goal: Find how many times 2 appears in the array

Step 1: Find first occurrence of 2 using binary search

[1, 2, 2, 2, 3, 4, 5]
          ↑
       first occurrence at index 1

Why: We need to know where the first 2 appears to start counting

Step 2: Find last occurrence of 2 using binary search

[1, 2, 2, 2, 3, 4, 5]
              ↑
         last occurrence at index 3

Why: We need to know where the last 2 appears to end counting

Step 3: Calculate count as last index - first index + 1

Count = 3 - 1 + 1 = 3

Why: Counting all elements from first to last occurrence gives total copies

Result:

[1, 2, 2, 2, 3, 4, 5]
Count of 2 is 3

Annotated Code

DSA Go

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 // record current match
			high = mid - 1 // search left half for earlier occurrence
		} else if arr[mid] < target {
			low = mid + 1 // target is right
		} else {
			high = mid - 1 // target is left
		}
	}
	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 // record current match
			low = mid + 1 // search right half for later occurrence
		} else if arr[mid] < target {
			low = mid + 1 // target is right
		} else {
			high = mid - 1 // target is left
		}
	}
	return result
}

func countOccurrences(arr []int, target int) int {
	first := firstOccurrence(arr, target)
	if first == -1 {
		return 0 // target not found
	}
	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 is %d\n", target, count)
}

result = mid // record current match high = mid - 1 // search left half for earlier occurrence

update result and move left to find first occurrence

result = mid // record current match low = mid + 1 // search right half for later occurrence

update result and move right to find last occurrence

if first == -1 { return 0 // target not found }

handle case when target is not in array

return last - first + 1

calculate total count from first and last indices

Output

Count of 2 is 3

Complexity Analysis

Time: O(log n) because we use binary search twice on the sorted array

Space: O(1) because we only use a few variables, no extra data structures

vs Alternative: Naive approach scans entire array O(n), this binary search method is faster for large sorted arrays

Edge Cases

empty array

returns 0 because target cannot be found

DSA Go

if first == -1 {
	return 0 // target not found
}

target not present in array

returns 0 because firstOccurrence returns -1

DSA Go

if first == -1 {
	return 0 // target not found
}

all elements are the target

returns length of array as count

DSA Go

return last - first + 1

When to Use This Pattern

When you see a sorted array and need to count how many times a number appears, use binary search to find first and last positions for an efficient count.

Common Mistakes

Mistake: Using linear scan instead of binary search, causing slow performance
Fix: Use binary search to find first and last occurrences to achieve O(log n) time

Mistake: Not updating search boundaries correctly when target is found
Fix: Move left boundary when searching for first occurrence and right boundary when searching for last occurrence

Summary

Counts how many times a target appears in a sorted array efficiently.

Use when you have a sorted list and want to quickly find the number of occurrences of a value.

The key is to find the first and last positions of the target using binary search, then count the elements between.