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

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Find first occurrence of target

↓

If not found -> return 0

↓

Find last occurrence of target

↓

Calculate count = last - first + 1

↓

Return count

↓

End

We first find where the target starts and ends in the sorted array, then count how many times it appears.

Execution Sample

DSA Rust

fn count_occurrences(arr: &[i32], target: i32) -> usize {
    let first = find_first(arr, target);
    if first.is_none() {
        return 0;
    }
    let last = find_last(arr, target);
    last.unwrap() - first.unwrap() + 1
}

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

Execution Table

Step	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Find first occurrence - mid calculation	mid=4	arr[4]=3 < target=5	left=5	[1,2,2,3,3,3,5,5,5,6]
2	Find first occurrence - mid calculation	mid=7	arr[7]=5 == target=5	right=7	[1,2,2,3,3,3,5,5,5,6]
3	Find first occurrence - mid calculation	mid=6	arr[6]=5 == target=5	right=6	[1,2,2,3,3,3,5,5,5,6]
4	Find first occurrence - mid calculation	mid=5	arr[5]=3 < target=5	left=6	[1,2,2,3,3,3,5,5,5,6]
5	First occurrence found at index 6	-	-	first=6	[1,2,2,3,3,3,5,5,5,6]
6	Find last occurrence - mid calculation	mid=7	arr[7]=5 == target=5	left=8	[1,2,2,3,3,3,5,5,5,6]
7	Find last occurrence - mid calculation	mid=8	arr[8]=5 == target=5	left=9	[1,2,2,3,3,3,5,5,5,6]
8	Find last occurrence - mid calculation	mid=9	arr[9]=6 > target=5	right=8	[1,2,2,3,3,3,5,5,5,6]
9	Last occurrence found at index 8	-	-	last=8	[1,2,2,3,3,3,5,5,5,6]
10	Calculate count	-	-	count=8 - 6 + 1 = 3	[1,2,2,3,3,3,5,5,5,6]
11	Return count	-	-	-	3

💡 Search ends after finding first and last occurrence indices and calculating count.

Variable Tracker

Variable	Start	After Step 5	After Step 9	Final
left	0	6	9	9
right	9	6	8	8
mid	-	5	9	9
first	None	6	6	6
last	None	None	8	8
count	None	None	None	3

Key Moments - 3 Insights

Why do we need to find both first and last occurrences?

Because the array is sorted, the target can appear multiple times in a row. Finding only one occurrence doesn't tell us how many times it appears. Steps 5 and 9 in the execution_table show how first and last indices are found to calculate the count.

What happens if the target is not in the array?

If the target is not found, the first occurrence search returns None (step 2). Then the function returns 0 immediately (step 3), as shown in the execution_table.

Why do we adjust left and right pointers differently in first and last occurrence searches?

For the first occurrence, when arr[mid] == target, we move right to mid to find the earliest index. For the last occurrence, we move left to mid + 1 to find the latest index. This is shown in steps 2-4 and 6-8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the first occurrence index found at step 5?

A 7

B 6

C 8

D 5

💡 Hint

Check the 'Pointer Changes' column at step 5 in the execution_table.

At which step does the last occurrence search update the right pointer to 8?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Pointer Changes' column for the last occurrence search steps in the execution_table.

If the target was 4 (not in array), what would the count returned be?

A 3

B 1

C 0

D Undefined

💡 Hint

Refer to the key_moments about target not found and step 3 in the execution_table.

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search twice: find first and last occurrence.
- First occurrence: move right pointer when arr[mid] == target.
- Last occurrence: move left pointer when arr[mid] == target.
- 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 find where it starts and ends. We do this by searching for the first and last positions of the target using binary search. If the target is not found, we return zero. Otherwise, the count is the difference between last and first positions plus one. This method is efficient because it uses the sorted order to quickly find boundaries. The execution table shows each step of the binary search adjusting pointers and checking values until the first and last occurrences are found. Then the count is calculated and returned.

Practice

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

easy

A. It counts 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 very fast on sorted arrays.

2. Step 2: Compare with linear search

   Linear search checks each element, which is slower (linear time). Binary search is faster (logarithmic time).

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
• Assuming binary search works on unsorted arrays
• Confusing counting with searching

2. Which Rust code snippet correctly declares a function to count occurrences of target in a sorted slice arr?

easy

A. fn count_occurrences(arr: &[i32], target: i32) -> usize { /* code */ }

B. fn count_occurrences(arr: Vec<i32>, target: i32) -> i32 { /* code */ }

C. fn count_occurrences(arr: &[i32], target: i32) -> i32 { /* code */ }

D. fn count_occurrences(arr: Vec<i32>, target: i32) -> usize { /* code */ }

Solution

1. Step 1: Check parameter types

   Using a slice &[i32] is efficient for read-only access without ownership transfer.

2. Step 2: Check return type

   Counting occurrences returns a non-negative number, so usize is appropriate.

3. Final Answer:

   fn count_occurrences(arr: &[i32], target: i32) -> usize { /* code */ } -> Option A

4. Quick Check:

   Slice + usize return = correct signature [OK]

Hint: Use slice &[i32] and usize for count [OK]

Common Mistakes:

• Using Vec when slice is enough
• Returning i32 instead of usize for counts
• Confusing ownership with borrowing

3. What is the output of this Rust code counting occurrences of 3 in the sorted array?

fn main() {
    let arr = [1, 2, 3, 3, 3, 3, 5];
    let count = count_occurrences(&arr, 3);
    println!("{}", count);
}

fn count_occurrences(arr: &[i32], target: i32) -> usize {
    let first = arr.binary_search(&target).unwrap_or_else(|x| x);
    let mut count = 0;
    for &num in &arr[first..] {
        if num == target {
            count += 1;
        } else {
            break;
        }
    }
    count
}

medium

A. 4

B. 3

C. 1

D. 0

Solution

1. Step 1: Find occurrence index

   binary_search returns Ok(index) for 3 at index 2.

2. Step 2: Count consecutive 3s from index 2

   Elements at indices 2,3,4,5 are 3, so count = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   4 occurrences counted correctly [OK]

Hint: Start counting from binary_search index [OK]

Common Mistakes:

• Using unwrap_or_else returns insertion point, not found index
• Counting beyond target elements
• Not breaking loop on different element

4. Identify the bug in this Rust function that counts occurrences of target in a sorted array arr:

fn count_occurrences(arr: &[i32], target: i32) -> usize {
    let start = arr.binary_search(&target).unwrap_or_else(|_| 0);
    let mut count = 0;
    for &num in &arr[start..] {
        if num == target {
            count += 1;
        } else {
            break;
        }
    }
    count
}

medium

A. Function returns i32 instead of usize

B. The loop does not break on different element

C. binary_search returns index of last occurrence, not first

D. unwrap_or_else(|_| 0) returns 0 even if target not found, causing wrong count

Solution

1. Step 1: Understand unwrap_or_else behavior

   unwrap_or_else(|_| 0) returns 0 if target not found, which is incorrect start index.

2. Step 2: Consequence of wrong start index

   Counting from 0 when target is absent counts wrong elements, giving wrong count.

3. Final Answer:

   unwrap_or_else(|_| 0) returns 0 even if target not found, causing wrong count -> Option D

4. Quick Check:

   unwrap_or_else should use insertion point or handle not found [OK]

Hint: Use unwrap_or_else with insertion point for not found [OK]

Common Mistakes:

• Using unwrap_or_else(|| 0)
• Not breaking loop on different element
• Confusing first and last occurrence index

5. Given a sorted array arr with possible duplicates, which Rust approach best counts occurrences of target efficiently and correctly for all cases, including when target is absent? Options: A) Use binary_search to find insertion points of target and target+1, then subtract indices. B) Use binary_search to find any occurrence, then count forward until different element. C) Use linear scan from start to end counting matches. D) Use binary_search to find last occurrence, then count backward until different element.

hard

A. Find one occurrence with binary_search, count forward until different element

B. Find insertion points for target and target+1, subtract to get count

C. Linear scan entire array counting matches

D. Find last occurrence with binary_search, count backward until different element

Solution

1. Step 1: Understand insertion points method

   Finding insertion points for target and target+1 gives start and end indices of target range.

2. Step 2: Calculate count by subtraction

   Subtracting these indices gives exact count, even if target is absent (count = 0).

3. Step 3: Compare with other methods

   Counting forward or backward after binary_search can fail if target not found; linear scan is slow.

4. Final Answer:

   Find insertion points for target and target+1, subtract to get count -> Option B

5. Quick Check:

   Insertion points subtraction = accurate count [OK]

Hint: Use binary_search for insertion points, subtract indices [OK]

Common Mistakes:

• Counting forward without checking if target found
• Using linear scan on large arrays
• Counting backward without binary_search for last occurrence