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

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Input: sorted array, target element

↓

Find first occurrence index using binary search

↓

Find last occurrence index using binary search

↓

Calculate count = last - first + 1

↓

Return count

↓

End

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

Execution Sample

DSA Javascript

function countOccurrences(arr, target) {
  const first = findFirst(arr, target);
  if (first === -1) return 0;
  const last = findLast(arr, target);
  return last - first + 1;
}

This code finds the first and last positions of the target in the sorted array and returns the count of occurrences.

Execution Table

Step	Operation	Array State	Pointer Changes	Visual State
1	Start countOccurrences(arr, 2)	[1,2,2,2,3,4,5]	first = undefined, last = undefined	Array unchanged
2	Call findFirst(arr, 2)	[1,2,2,2,3,4,5]	low=0, high=6, mid=3	Check arr[3]=2 matches target
3	findFirst: arr[3]=2 matches target	Same	high=2 (move left)	Searching left half
4	findFirst: low=0, high=2, mid=1	Same	arr[1]=2 matches target	high=0 (move left)
5	findFirst: low=0, high=0, mid=0	Same	arr[0]=1 < target	low=1 (move right)
6	findFirst: low=1, high=0 (low>high)	Same	Return first=1	First occurrence at index 1
7	Call findLast(arr, 2)	[1,2,2,2,3,4,5]	low=0, high=6, mid=3	Check arr[3]=2 matches target
8	findLast: arr[3]=2 matches target	Same	low=4 (move right)	Searching right half
9	findLast: low=4, high=6, mid=5	Same	arr[5]=4 > target	high=4 (move left)
10	findLast: low=4, high=4, mid=4	Same	arr[4]=3 > target	high=3 (move left)
11	findLast: low=4, high=3 (low>high)	Same	Return last=3	Last occurrence at index 3
12	Calculate count = last - first + 1	Same	count = 3 - 1 + 1 = 3	Count of 2 is 3
13	Return count=3	Same	Function ends	Final result: 3 occurrences

💡 Binary searches end when low > high; count calculated from first and last indices.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 7	After Step 11	After Step 12	Final
first	undefined	undefined	1	1	1	1	1
last	undefined	undefined	undefined	undefined	3	3	3
low	undefined	0	1	0	4	4	4
high	undefined	6	0	6	3	3	3
mid	undefined	3	0	3	4	4	4
count	undefined	undefined	undefined	undefined	undefined	3	3

Key Moments - 3 Insights

Why do we need two binary searches instead of one?

One binary search finds the first occurrence (step 6), the other finds the last occurrence (step 11). This ensures we count all occurrences between these indices.

What happens if the target is not found?

If findFirst returns -1 (not found), countOccurrences returns 0 immediately (step 2), skipping findLast.

Why does findFirst move 'high' when arr[mid] equals target?

To find the first occurrence, we continue searching left (lower indices) by moving 'high' left (step 3 and 4) even if we find the target.

Visual Quiz - 3 Questions

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

A 1

B 0

C -1

D 3

💡 Hint

Check the 'Pointer Changes' column at step 6 where findFirst returns the first occurrence index.

At which step does the condition low > high become true for findLast?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at the 'Pointer Changes' column for findLast where low=4 and high=3 indicating low > high.

If the target was not in the array, what would be the output of countOccurrences?

A Length of the array

B 0

C -1

D 1

💡 Hint

Refer to step 2 where if findFirst returns -1, countOccurrences returns 0 immediately.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: findFirst and findLast occurrence
- findFirst moves left when target found
- findLast moves right when target found
- Count = last - first + 1
- If not found, count = 0

Full Transcript

To count how many times an element appears in a sorted array, we use two binary searches. First, find the first position where the element appears. Then, find the last position. The count is the difference plus one. If the element is not found, return zero. This method is efficient because it uses binary search, which runs fast on sorted arrays.