Count Occurrences of Element in Sorted Array in DSA Go - Execution Trace

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Find first occurrence of target using binary search

↓

Find last occurrence of target using binary search

↓

Calculate count = last_index - first_index + 1

↓

Return count

↓

End

We use two binary searches to find the first and last positions of the target, then count how many times it appears.

Execution Sample

DSA Go

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

This code finds the first and last positions of the target in a sorted array and returns how many times it occurs.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start binary search for first occurrence	[1,2,2,2,3,4,5]	low=0, high=6	Array unchanged
2	Mid calculation	[1,2,2,2,3,4,5]	mid=3 (value=2)	Check mid value
3	Check if mid is first occurrence	Same	mid=3, mid-1=2 (value=2)	Not first, move high to mid-1=2
4	Update pointers	Same	low=0, high=2	Narrow search to left half
5	Mid calculation	Same	mid=1 (value=2)	Check mid value
6	Check if mid is first occurrence	Same	mid=1, mid-1=0 (value=1)	Yes, first occurrence found at index 1
7	Start binary search for last occurrence	Same	low=0, high=6	Array unchanged
8	Mid calculation	Same	mid=3 (value=2)	Check mid value
9	Check if mid is last occurrence	Same	mid=3, mid+1=4 (value=3)	Yes, last occurrence found at index 3
10	Calculate count	Same	count = 3 - 1 + 1 = 3	Count of target is 3
11	Return count	Same	Return 3	Done
12	Exit	Same	-	Target count returned

💡 Binary searches complete, count calculated and returned

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
low	0	0	0	0	0
high	6	2	2	6	6
mid	-	3	1	3	3
first	-1	-1	1	1	1
last	-1	-1	-1	3	3
count	-	-	-	-	3

Key Moments - 3 Insights

Why do we need two separate binary searches for first and last occurrences?

Because the target can appear multiple times, one search finds the earliest index, the other finds the latest. See steps 3-6 for first occurrence and 8-9 for last occurrence.

What if the target is not in the array?

The first binary search returns -1 (step 6), so the function returns 0 immediately (step 3 in code).

Why do we check mid-1 and mid+1 values during binary search?

To confirm if mid is the first or last occurrence by checking neighbors. If neighbors are different, mid is boundary. See steps 3 and 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'mid' at step 6?

A 1

B 3

C 0

D 2

💡 Hint

Check the 'Pointer Changes' column at step 6 in the execution table.

At which step does the binary search find the last occurrence of the target?

A Step 3

B Step 6

C Step 9

D Step 2

💡 Hint

Look for 'last occurrence found' in the 'Operation' column.

If the target is not found, what does the function return according to the execution flow?

A 1

B 0

C -1

D Array length

💡 Hint

See the code snippet and key moment about target absence.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: find first and last index of target
- First occurrence: move left if duplicates found
- Last occurrence: move right if duplicates found
- Count = last_index - first_index + 1
- Return 0 if target not found

Full Transcript

To count how many times a number appears in a sorted array, we do two binary searches. First, we find the earliest place the number appears. Then, we find the latest place it appears. The count is the difference between these two positions plus one. If the number is not found, we return zero. This method is fast because binary search quickly narrows down the search area by checking the middle element and moving left or right accordingly.