Count Occurrences of Element in Sorted Array in DSA C++ - Execution Trace

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Input: Sorted Array, Target Element

↓

Find First Occurrence Index

↓

Find Last Occurrence Index

↓

Calculate Count = Last - First + 1

↓

Return Count

↓

End

We find where the target first appears, then where it last appears, then count how many times it occurs.

Execution Sample

DSA C++

int countOccurrences(int arr[], int n, int x) {
  int first = findFirst(arr, n, x);
  if (first == -1) return 0;
  int last = findLast(arr, n, x);
  return last - first + 1;
}

This code finds the first and last positions of x in a sorted array and returns how many times x appears.

Execution Table

Step	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Find First Occurrence	mid=4	arr[4]=5 == 5	high=4	[1,2,3,4,5,5,5,6,7]
2	Find First Occurrence	mid=1	arr[1]=2 < 5	low=2	[1,2,3,4,5,5,5,6,7]
3	Find First Occurrence	mid=3	arr[3]=4 < 5	low=4	[1,2,3,4,5,5,5,6,7]
4	Find First Occurrence	mid=4	arr[4]=5 == 5	high=4	[1,2,3,4,5,5,5,6,7]
5	Find First Occurrence	mid=4	arr[4]=5 == 5	high=3	[1,2,3,4,5,5,5,6,7]
6	First Occurrence Found	index=4	-	-	[1,2,3,4,5,5,5,6,7]
7	Find Last Occurrence	mid=6	arr[6]=5 == 5	low=7	[1,2,3,4,5,5,5,6,7]
8	Find Last Occurrence	mid=7	arr[7]=6 > 5	high=6	[1,2,3,4,5,5,5,6,7]
9	Find Last Occurrence	mid=6	arr[6]=5 == 5	low=7	[1,2,3,4,5,5,5,6,7]
10	Last Occurrence Found	index=6	-	-	[1,2,3,4,5,5,5,6,7]
11	Calculate Count	-	-	-	Count = 6 - 4 + 1 = 3
12	Return Count	-	-	-	3

💡 Search ends when low > high or first/last occurrence found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
low (first)	0	0	2	4	4	4	4	4	4	4	4	4
high (first)	8	4	4	4	3	3	3	3	3	3	3	3
mid (first)	-	4	1	3	4	4	-	-	-	-	-	-
firstIndex	-1	-1	-1	-1	-1	4	4	4	4	4	4	4
low (last)	0	0	0	0	0	0	0	7	7	7	7	7
high (last)	8	8	8	8	8	8	8	8	6	6	6	6
mid (last)	-	-	-	-	-	-	-	6	7	6	-	-
lastIndex	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	6	6
count	-	-	-	-	-	-	-	-	-	-	-	3

Key Moments - 3 Insights

Why do we update 'high' when arr[mid] == x in findFirst?

Because we want to find the earliest index where x appears, so we move 'high' left to continue searching earlier positions (see steps 1,4,5).

Why do we update 'low' when arr[mid] == x in findLast?

Because we want to find the last occurrence, so we move 'low' right to search later positions (see steps 7,9).

What if the element is not found at all?

The first occurrence search returns -1, so countOccurrences returns 0 immediately (not shown in this example).

Visual Quiz - 3 Questions

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

A 4

B 3

C -1

D 6

💡 Hint

Check the 'firstIndex' variable in variable_tracker after step 6.

At which step does the 'lastIndex' get assigned its final value?

A Step 9

B Step 10

C Step 7

D Step 11

💡 Hint

Look at the execution_table row where 'Last Occurrence Found' is noted.

If the target element was not in the array, what would the count be?

A 1

B -1

C 0

D Array length

💡 Hint

Refer to the key moment about element not found and the early return in code.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: find first and last occurrence of target.
- For first occurrence: move high when arr[mid] == target.
- For last occurrence: move low when arr[mid] == target.
- Count = lastIndex - firstIndex + 1.
- If not found, count is 0.

Full Transcript

To count how many times an element appears in a sorted array, we find the first and last positions where it appears using binary search. We adjust pointers to narrow down the search: for the first occurrence, we move the high pointer left when we find the target; for the last occurrence, we move the low pointer right. The count is the difference between these positions plus one. If the element is not found, the count is zero.