Count Occurrences of Element in Sorted Array in DSA Javascript - 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 array. Since the array is sorted, all occurrences of the element are grouped together. This makes it easier and faster to count them than in an unsorted array. The goal is to find the count efficiently without checking every element one by one.

Why it matters

Without this method, counting occurrences would require checking every element, which can be slow for large arrays. Efficient counting saves time and computing power, especially in applications like searching databases, text processing, or analytics. It helps programs run faster and handle bigger data smoothly.

Where it fits

Before learning this, you should understand arrays and basic searching techniques like linear and binary search. After this, you can learn about more advanced searching and sorting algorithms, and how to handle data efficiently in real-world problems.

Mental Model

Core Idea

In a sorted array, all copies of the same element are next to each other, 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 just find the first and last copy on the shelf and count the books in between, instead of checking every book.

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

Indexes: 0  1  2  3  4  5  6
Values:  1 [2][2][2] 3  4  5

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 of numbers arranged from smallest to largest (or vice versa). 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 are grouped together in sorted arrays.

Understanding that duplicates are grouped helps us avoid checking the whole array to count occurrences.

2

Foundation

Basic Counting by Linear Search

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

Start from the beginning of the array and check each element. Increase a counter when you find the target element. Stop when you reach the end or find a different element after the target group.

Result

You get the count but it can be slow for large arrays.

Counting by checking every element works but is inefficient for big data.

3

Intermediate

Using Binary Search to Find First Occurrence

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

Concept: Modify binary search to find the first position where the target appears.

Binary search splits the array in half repeatedly to find the target quickly. To find the first occurrence, when you find the target, keep searching the left half to see if it appears earlier. Stop when you can't find it earlier.

Result

You get the index of the first occurrence of the target.

Knowing how to tweak binary search to find boundaries is key to efficient counting.

4

Intermediate

Using Binary Search to Find Last Occurrence

🤔Before reading on: do you think finding the last occurrence is similar to finding the first? Commit to your answer.

Concept: Modify binary search to find the last position where the target appears.

Similar to the first occurrence, but when you find the target, search the right half to find if it appears later. Stop when you can't find it later.

Result

You get the index of the last occurrence of the target.

Finding both ends lets you calculate the count without scanning the whole array.

5

Intermediate

Calculating Count from Boundaries

Concept: Use the first and last occurrence indexes to find how many times the element appears.

Count = (last occurrence index) - (first occurrence index) + 1. For example, if first is 2 and last is 4, count = 4 - 2 + 1 = 3.

Result

You get the total number of occurrences quickly.

Simple math on indexes replaces slow counting loops.

6

Advanced

Complete JavaScript Implementation

🤔Before reading on: do you think the code should handle cases where the element is not found? Commit to your answer.

Concept: Write full code using binary search to count occurrences, including edge cases.

function countOccurrences(arr, target) { function findFirst() { let left = 0, right = arr.length - 1, result = -1; while (left <= right) { let mid = Math.floor(left + (right - left) / 2); if (arr[mid] === target) { result = mid; right = mid - 1; // search left side } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } function findLast() { let left = 0, right = arr.length - 1, result = -1; while (left <= right) { let mid = Math.floor(left + (right - left) / 2); if (arr[mid] === target) { result = mid; left = mid + 1; // search right side } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } const first = findFirst(); if (first === -1) return 0; // target not found const last = findLast(); return last - first + 1; } // Example: // countOccurrences([1,2,2,2,3,4,5], 2) returns 3

Result

The function returns the correct count or 0 if not found.

Handling edge cases ensures the method works reliably in all situations.

7

Expert

Optimizing for Repeated Queries

🤔Before reading on: do you think running binary search every time is best for many queries? Commit to your answer.

Concept: Use preprocessing or data structures to speed up counting when many queries happen on the same array.

If you need to count occurrences of many different elements repeatedly, building an index like a hash map or segment tree can help. For example, a map from element to its first and last occurrence indexes lets you answer queries in constant time after setup.

Result

Counting queries become much faster after preprocessing.

Knowing when to trade setup time for faster queries is key in real-world applications.

Under the Hood

Binary search works by repeatedly dividing the search space in half, comparing the middle element to the target. To find first or last occurrence, the search continues in one half even after finding the target, narrowing down the boundary. This avoids scanning the whole array and reduces time from linear to logarithmic.

Why designed this way?

The method leverages the sorted order to avoid unnecessary checks. Early computer scientists designed binary search to speed up searching in sorted data. Extending it to find boundaries is a natural evolution to solve counting problems efficiently.

Array indexes: 0  1  2  3  4  5  6
Values:        1 [2][2][2] 3  4  5

Binary Search Steps:
 ┌─────────────┐
 │Start: left=0│
 │right=6      │
 └─────┬───────┘
       ↓
 ┌─────────────┐
 │mid=3, value=2│
 └─────┬───────┘
       ↓
Search left half for first occurrence
       ↓
 ┌─────────────┐
 │mid=1, value=2│
 └─────┬───────┘
       ↓
No earlier 2 found, first occurrence=1

Similarly for last occurrence, search right half after finding target.

Myth Busters - 4 Common Misconceptions

Quick: Does binary search always find the first occurrence of a target in a sorted array? Commit yes or no.

Common Belief: Binary search always returns the first occurrence of the target.

Reality: Standard binary search returns any occurrence, not necessarily the first or last.

Why it matters: Assuming it finds the first occurrence can cause wrong counts and bugs in programs.

Quick: Is counting occurrences in a sorted array always faster than in an unsorted one? Commit yes or no.

Common Belief: Counting occurrences is always faster in a sorted array.

Reality: If you do a simple linear count, sorted or not, time is the same; the speedup comes only when using binary search.

Why it matters: Without using binary search, you miss the main advantage of sorting for counting.

Quick: Can you use this counting method if the array is not sorted? Commit yes or no.

Common Belief: This method works on any array, sorted or not.

Reality: It only works correctly on sorted arrays because duplicates must be grouped.

Why it matters: Using it on unsorted arrays leads to incorrect counts and wasted effort.

Quick: Does the count equal last index minus first index? Commit yes or no.

Common Belief: Count equals last index minus first index.

Reality: Count equals last index minus first index plus one, because indexes start at zero.

Why it matters: Missing the +1 causes off-by-one errors, leading to wrong counts.

Expert Zone

1

Binary search for boundaries must carefully adjust mid calculation and loop conditions to avoid infinite loops or missing edge cases.

2

When the array contains many duplicates, caching first and last occurrences can save repeated binary searches.

3

In some languages or environments, integer overflow can happen when calculating mid as (left + right) / 2; using left + (right - left) / 2 is safer.

When NOT to use

If the array is unsorted or changes frequently, this method is not suitable. Instead, use hash maps or balanced trees for dynamic counting. For small arrays, simple linear counting may be faster due to lower overhead.

Production Patterns

In databases and search engines, counting occurrences is done using indexes that store boundary positions. In text processing, suffix arrays or trees help count repeated patterns efficiently. Real systems combine binary search with caching and preprocessing for speed.

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 provide a different way to count occurrences in unsorted or dynamic data, showing how data structure choice depends on data properties.

Text Search Algorithms

Similar pattern

Counting repeated patterns in text uses similar boundary-finding ideas, linking array counting to string processing.

Common Pitfalls

#1 Off-by-one error in count calculation

Wrong approach:

count = lastIndex - firstIndex;

Correct approach:

count = lastIndex - firstIndex + 1;

Root cause:

Forgetting that indexes start at zero and both ends are inclusive.

#2 Using standard binary search without boundary checks

Wrong approach:

function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}

Correct approach:

function findFirst(arr, target) {
let left = 0, right = arr.length - 1, result = -1;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (arr[mid] === target) {
result = mid;
right = mid - 1;
} else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}

Root cause:

Not adjusting search boundaries to find first or last occurrence.

#3 Applying method on unsorted array

Wrong approach:

countOccurrences([3,1,2,2,5], 2) // using binary search method

Correct approach:

Use linear count or hash map for unsorted arrays.

Root cause:

Assuming sorted property without verifying array order.

Key Takeaways

Counting occurrences in a sorted array is efficient because duplicates are grouped together.

Binary search can be modified to find the first and last positions of a target element.

The count is calculated by subtracting the first index from the last and adding one.

Handling edge cases like element not found is crucial for reliable code.

For repeated queries, preprocessing or alternative data structures can improve performance.