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.

Practice

1. What is the main advantage of using a binary search approach to count occurrences of an element in a sorted array?

easy

A. It counts all elements without searching.

B. It sorts the array automatically.

C. It reduces the search time to logarithmic complexity.

D. It works only on unsorted arrays.

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, making it faster than linear search.

2. Step 2: Apply to counting occurrences

   By finding the first and last positions of the element, we can count occurrences efficiently.

3. Final Answer:

   It reduces the search time to logarithmic complexity. -> Option C

4. Quick Check:

   Binary search = O(log n) time [OK]

Hint: Binary search halves search space each step [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Using linear search for counting in sorted array
• Assuming binary search works on unsorted arrays

2. Which Go code snippet correctly declares a function to count occurrences of an integer in a sorted slice?

easy

A. func countOccurrences(arr []int, target int) int { return 0 }

B. func countOccurrences(arr int[], target int) int { return 0 }

C. func countOccurrences(arr []int, target int) string { return "0" }

D. func countOccurrences(arr []int, target int) { return 0 }

Solution

1. Step 1: Check function signature syntax

   In Go, slices are declared as []int, and return type int is correct for count.

2. Step 2: Validate return statement matches return type

   Returning 0 as int matches the return type int.

3. Final Answer:

   func countOccurrences(arr []int, target int) int { return 0 } -> Option A

4. Quick Check:

   Correct Go function syntax [OK]

Hint: Use []int for slices and match return type [OK]

Common Mistakes:

• Using array syntax int[] instead of []int
• Mismatching return type and return value
• Omitting return type in function signature

3. What will be the output of the following Go code snippet?

func countOccurrences(arr []int, target int) int {
    left := 0
    right := len(arr) - 1
    first := -1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            first = mid
            right = mid - 1
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if first == -1 {
        return 0
    }
    left = 0
    right = len(arr) - 1
    last := -1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            last = mid
            left = mid + 1
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return last - first + 1
}

func main() {
    arr := []int{1, 2, 2, 2, 3, 4, 5}
    count := countOccurrences(arr, 2)
    fmt.Println(count)
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Find first occurrence of 2

   Binary search finds first index of 2 at position 1.

2. Step 2: Find last occurrence of 2

   Binary search finds last index of 2 at position 3.

3. Step 3: Calculate count

   Count = last - first + 1 = 3 - 1 + 1 = 3.

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Occurrences of 2 = 3 [OK]

Hint: Find first and last index, then subtract [OK]

Common Mistakes:

• Returning index instead of count
• Not updating left/right correctly in binary search
• Confusing first and last occurrence indices

4. Identify the bug in the following Go function that counts occurrences of a target in a sorted array:

func countOccurrences(arr []int, target int) int {
    left, right := 0, len(arr)-1
    count := 0
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            count++
            break
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return count
}

medium

A. It counts only one occurrence, not all.

B. It causes an infinite loop.

C. It returns the index instead of count.

D. It does not handle empty arrays.

Solution

1. Step 1: Analyze loop behavior

   The loop breaks after finding one occurrence, so count increments only once.

2. Step 2: Understand counting logic

   Counting all occurrences requires searching for first and last positions, not just one match.

3. Final Answer:

   It counts only one occurrence, not all. -> Option A

4. Quick Check:

   Loop breaks early, count = 1 [OK]

Hint: Break stops counting after first match [OK]

Common Mistakes:

• Using break instead of continuing search
• Not searching for first and last indices
• Assuming one match equals total count

5. Given a sorted array with possible duplicates, how would you modify the binary search approach to count occurrences of multiple target values efficiently? Choose the best approach.

hard

A. Perform separate binary searches for first and last occurrences of each target, then sum counts.

B. Use a linear scan for each target to count occurrences.

C. Sort the array again before counting each target.

D. Use a hash map to store counts after one full scan.

Solution

1. Step 1: Consider efficiency for multiple targets

   Binary search per target is O(k log n) for k targets, which can be costly.

2. Step 2: Use hash map after one scan

   A single linear scan builds a map of counts for all elements in O(n), allowing O(1) lookup per target.

3. Step 3: Compare approaches

   Hash map approach is more efficient for multiple queries than repeated binary searches.

4. Final Answer:

   Use a hash map to store counts after one full scan. -> Option D

5. Quick Check:

   Hash map = efficient multiple counts [OK]

Hint: Build counts once, then query fast [OK]

Common Mistakes:

• Repeating binary search for each target
• Sorting array multiple times unnecessarily
• Ignoring hash map for frequency counting