Count Occurrences of Element in Sorted Array in DSA Rust

Mental Model

We find how many times a number appears in a sorted list by locating its first and last positions.

Analogy: Imagine a row of identical books sorted by title. To count how many copies of one title are there, find the first copy and the last copy, then count all 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], target: 2

Goal: Find how many times 2 appears in the array

Step 1: Find first occurrence of 2 using binary search

mid at index 3 (value 2), move left to find first occurrence
Array: [1, 2, 2, 2, 3, 4, 5]

Why: We want the earliest position where 2 appears

Step 2: Adjust search to left half, mid at index 1 (value 2), move left again

mid at index 1 (value 2), check if previous is 0 (value 1), so first occurrence found at index 1

Why: Index 1 is the first place 2 appears

Step 3: Find last occurrence of 2 using binary search

mid at index 3 (value 2), move right to find last occurrence

Why: We want the last place 2 appears

Step 4: Adjust search to right half, mid at index 3 (value 2), check next index 4 (value 3), last occurrence found at index 3

last occurrence at index 3

Why: Index 3 is the last place 2 appears

Step 5: Calculate count as last - first + 1 = 3 - 1 + 1 = 3

Count of 2 is 3

Why: Number of times 2 appears is the distance between first and last plus one

Result:

Array: [1, 2, 2, 2, 3, 4, 5]
Count of 2: 3

Annotated Code

DSA Rust

fn find_first_occurrence(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().wrapping_sub(1);
    let mut result = None;
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid] == target {
            result = Some(mid);
            if mid == 0 {
                break; // first element is target
            }
            high = mid - 1; // search left half
        } else if arr[mid] < target {
            low = mid + 1; // search right half
        } else {
            if mid == 0 { break; } // prevent underflow
            high = mid - 1; // search left half
        }
    }
    result
}

fn find_last_occurrence(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len().wrapping_sub(1);
    let mut result = None;
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid] == target {
            result = Some(mid);
            low = mid + 1; // search right half
        } else if arr[mid] < target {
            low = mid + 1; // search right half
        } else {
            if mid == 0 { break; } // prevent underflow
            high = mid - 1; // search left half
        }
    }
    result
}

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

fn main() {
    let arr = [1, 2, 2, 2, 3, 4, 5];
    let target = 2;
    let count = count_occurrences(&arr, target);
    println!("Array: {:?}\nCount of {}: {}", arr, target, count);
}

if arr[mid] == target { result = Some(mid); high = mid - 1; }

move left to find first occurrence after finding target

if arr[mid] == target { result = Some(mid); low = mid + 1; }

move right to find last occurrence after finding target

if first.is_none() { return 0; }

handle case when target not found

last - first.unwrap() + 1

calculate count from first and last positions

Output

Array: [1, 2, 2, 2, 3, 4, 5]

Count of 2: 3

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans entire array O(n), this uses binary search O(log n) for faster counting

Edge Cases

empty array

returns 0 because target cannot be found

DSA Rust

if first.is_none() { return 0; }

target not in array

returns 0 because no occurrences

DSA Rust

if first.is_none() { return 0; }

all elements are target

returns length of array as count

DSA Rust

last - first.unwrap() + 1

When to Use This Pattern

When you need to count how many times a number appears in a sorted list, use binary search to find first and last positions for efficient counting.

Common Mistakes

Mistake: Not updating search boundaries correctly when target is found, causing infinite loops or wrong results.
Fix: After finding target, move left boundary for first occurrence search and right boundary for last occurrence search.

Summary

Counts how many times a target appears in a sorted array using binary search.

Use when you want fast counting of elements in a sorted list without scanning all elements.

The key is to find the first and last positions of the target, then calculate the count from their difference.

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