Count Occurrences of Element in Sorted Array in DSA Rust - Deep Dive

Overview - Count Occurrences of Element in Sorted Array

What is it?

Counting occurrences of an element in a sorted array means finding how many times that element appears in the list. Since the array is sorted, all copies of the element are grouped together. This makes it easier and faster to count them than searching the whole array. We use special methods to find the start and end positions of the element quickly.

Why it matters

Without this method, counting occurrences would require checking every item, which is slow for large lists. Efficient counting helps in many real-world tasks like searching databases, analyzing data, or processing logs where speed matters. It saves time and computing power, making programs faster and more responsive.

Where it fits

Before this, you should understand arrays and basic searching methods like linear and binary search. After this, you can learn about more complex searching and sorting algorithms, or how to handle unsorted data efficiently.

Mental Model

Core Idea

In a sorted array, all copies of an element are together, so finding the first and last position of that element lets you count its occurrences quickly.

Think of it like...

Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title you have, you find the first copy and the last copy on the shelf, then count all books between them.

Sorted Array: [1, 2, 2, 2, 3, 4, 5]
Element to count: 2
Find first 2 at index 1
Find last 2 at index 3
Count = last - first + 1 = 3

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why elements are grouped.

A sorted array is a list where elements are arranged in order, like numbers from smallest to largest. Because of this order, if an element appears multiple times, all its copies are next to each other. For example, in [1, 2, 2, 3], the two 2s are side by side.

Result

You know that duplicates in a sorted array are always together.

Understanding that duplicates are grouped lets us use faster methods than checking every element.

2

Foundation

Basic Counting by Scanning

Concept: Count occurrences by checking each element one by one.

To count how many times an element appears, you can look at each item and add one if it matches. For example, to count 2 in [1, 2, 2, 3], check each element: 1 (no), 2 (yes), 2 (yes), 3 (no). Total count is 2.

Result

Count is 2 for element 2 in the example array.

This method works but is slow for big arrays because it checks every element.

3

Intermediate

Using Binary Search to Find Positions

🤔Before reading on: do you think binary search can find the first occurrence of an element directly, or only any occurrence? Commit to your answer.

Concept: Binary search can be adapted to find the first or last position of an element in a sorted array.

Binary search splits the array in half repeatedly to find an element quickly. To find the first occurrence, when you find the element, you keep searching the left half to see if it appears earlier. Similarly, to find the last occurrence, you search the right half after finding the element.

Result

You can find the first and last positions of an element in O(log n) time.

Knowing how to adjust binary search to find boundaries is key to fast counting.

4

Intermediate

Calculating Count from Positions

🤔Before reading on: if the first occurrence is at index 3 and last at index 7, how many times does the element appear? Commit to your answer.

Concept: Count equals last position minus first position plus one.

If the first occurrence is at index f and last at index l, then count = l - f + 1. For example, if first is 3 and last is 7, count = 7 - 3 + 1 = 5.

Result

You get the total number of occurrences without scanning the whole array.

This simple formula leverages the sorted property to avoid extra work.

5

Intermediate

Implementing in Rust with Binary Search

🤔Before reading on: do you think Rust's standard library binary_search returns the first occurrence index or any occurrence? Commit to your answer.

Concept: Rust's binary_search returns any matching index; we need custom code to find first and last occurrences.

Rust's binary_search returns Ok(index) if found, but not guaranteed first or last. We write two functions: one to find first occurrence by moving left when possible, and one for last occurrence by moving right. Then count is last - first + 1 or zero if not found.

Result

Efficient Rust code that counts occurrences in O(log n) time.

Understanding Rust's binary_search behavior helps write precise code for counting.

6

Advanced

Handling Edge Cases and Empty Results

🤔Before reading on: if the element is not in the array, what should the count be? Commit to your answer.

Concept: If the element is missing, count must be zero, and code must handle this gracefully.

When binary search fails, it returns Err. Our code checks this and returns zero count. Also, if first or last positions are invalid or inconsistent, count is zero. This prevents wrong counts or crashes.

Result

Robust counting that works even if element is absent.

Handling missing elements prevents bugs and ensures reliable results.

7

Expert

Optimizing with Standard Library and Unsafe Code

🤔Before reading on: do you think using unsafe Rust can speed up counting significantly? Commit to your answer.

Concept: Advanced Rust code can use unsafe blocks or specialized crates to optimize performance, but with tradeoffs.

Unsafe Rust can avoid bounds checks or use SIMD instructions for faster searches. Also, crates like 'slice_binary_search' provide more control. However, these add complexity and risk. Usually, standard safe Rust with binary search is enough.

Result

Potential speed gains in critical systems, balanced with safety concerns.

Knowing when and how to optimize beyond safe Rust is key for expert performance tuning.

Under the Hood

Binary search works by repeatedly dividing the array in half and comparing the middle element to the target. For counting occurrences, we modify binary search to find the boundary indices where the element first and last appears. This uses comparisons and index adjustments to narrow down the exact positions without scanning the whole array.

Why designed this way?

Binary search was designed to reduce search time from linear to logarithmic by exploiting sorted order. Modifying it to find boundaries leverages the same principle to count duplicates efficiently. Alternatives like linear scan are simpler but slower, so this method balances speed and complexity.

Sorted Array Indices: 0 1 2 3 4 5 6 7
Values:           [1 2 2 2 3 4 5 5]
Search for 2:
 ┌───────────────┐
 │ Binary Search │
 └───────────────┘
  ↓
Find middle index 3 (value 2)
Check left half for first occurrence
Check right half for last occurrence
Result: first=1, last=3
Count = 3 - 1 + 1 = 3

Myth Busters - 4 Common Misconceptions

Quick: does binary_search in Rust always return the first occurrence index? Commit yes or no.

Common Belief: Rust's binary_search returns the first occurrence of the element.

Reality: It returns any matching index, not guaranteed first or last.

Why it matters: Assuming it returns the first occurrence can cause wrong counts or missed duplicates.

Quick: if an element is not in the array, does binary_search return -1? Commit yes or no.

Common Belief: If the element is missing, binary_search returns -1 or an error code.

Reality: It returns Err with the index where the element could be inserted to keep order.

Why it matters: Misunderstanding this leads to incorrect handling of missing elements and bugs.

Quick: can counting occurrences be done faster than O(log n) in a sorted array? Commit yes or no.

Common Belief: Counting occurrences can be done in constant time if the array is sorted.

Reality: Counting requires at least O(log n) time to find boundaries; constant time is impossible without extra data structures.

Why it matters: Expecting constant time leads to wrong assumptions about performance and design.

Quick: does scanning the whole array always give the correct count? Commit yes or no.

Common Belief: Scanning the entire array is the only way to count occurrences correctly.

Reality: In sorted arrays, binary search methods are faster and equally correct.

Why it matters: Ignoring binary search wastes time and resources on large data.

Expert Zone

1

Binary search for boundaries must carefully handle equal elements to avoid infinite loops or off-by-one errors.

2

Rust's standard library binary_search is optimized but limited; custom implementations can provide more control for counting.

3

In concurrent or mutable contexts, the array might change between searches, requiring synchronization or atomic operations.

When NOT to use

If the array is unsorted, binary search methods fail; use hash maps or linear scans instead. For very small arrays, simple scanning may be faster due to lower overhead.

Production Patterns

Counting occurrences in sorted logs or event streams for analytics, using binary search to quickly summarize data. Also used in database indexing and search engines to count matching records efficiently.

Connections

Binary Search

Builds-on

Understanding binary search is essential because counting occurrences in sorted arrays is a direct application of finding boundaries using binary search.

Hash Maps

Alternative approach

Hash maps count occurrences in unsorted data efficiently, showing different tradeoffs between sorting and hashing.

Signal Processing

Pattern detection analogy

Counting repeated signals in sorted time series data is similar to counting occurrences in arrays, linking data structures to real-world signal analysis.

Common Pitfalls

#1 Assuming binary_search returns the first occurrence index.

Wrong approach:

let index = arr.binary_search(&target).unwrap(); // use index as first occurrence

Correct approach:

let first = find_first_occurrence(&arr, target); // custom function to find first

Root cause:

Misunderstanding Rust's binary_search behavior leads to incorrect counting.

#2 Not handling the case when element is missing.

Wrong approach:

let count = last - first + 1; // without checking if element exists

Correct approach:

if first.is_none() { count = 0 } else { count = last - first + 1 }

Root cause:

Ignoring error results from binary_search causes wrong counts or panics.

#3 Using linear scan on large sorted arrays.

Wrong approach:

let count = arr.iter().filter(|&&x| x == target).count();

Correct approach:

Use binary search to find boundaries and calculate count in O(log n).

Root cause:

Not leveraging sorted property wastes performance.

Key Takeaways

In sorted arrays, duplicates are grouped, enabling fast counting by finding first and last positions.

Binary search can be adapted to find these boundary positions efficiently in logarithmic time.

Rust's standard binary_search returns any matching index, so custom code is needed to find exact boundaries.

Handling missing elements and edge cases is crucial for correct and robust counting.

Advanced optimizations exist but safe binary search methods are sufficient for most practical uses.

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