Count Occurrences of Element in Sorted Array in DSA Javascript

Mental Model

In a sorted list, all copies of the same number are next to each other. We find where the number starts and ends to count how many times it appears.

Analogy: Imagine a row of identical books on a shelf. To count how many copies of one title there are, you find the first copy and the last copy, then count all books in between.

Sorted array: [1, 2, 2, 2, 3, 4]
Find occurrences of 2:
Positions: 0  1  2  3  4  5
Values:    1 -> 2 -> 2 -> 2 -> 3 -> 4
             ↑          ↑
         first 2     last 2

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4], target: 2

Goal: Count how many times 2 appears in the sorted array

Step 1: Find first position of 2 using binary search

Array: [1, 2, 2, 2, 3, 4]
Check middle index 2 -> value 2 matches target
Move search to left half to find first occurrence

Why: We want the earliest place 2 appears

Step 2: Narrow search to left half, check index 1 -> value 2 matches target

Array: [1, 2, 2, 2, 3, 4]
Index 1 is 2, check if it's first or move left

Why: Check if this is the first 2 or if earlier 2 exists

Step 3: Check index 0 -> value 1 less than target, so first occurrence is at index 1

Array: [1, 2, 2, 2, 3, 4]
First 2 found at index 1

Why: No earlier 2 found, so index 1 is first occurrence

Step 4: Find last position of 2 using binary search

Array: [1, 2, 2, 2, 3, 4]
Check middle index 2 -> value 2 matches target
Move search to right half to find last occurrence

Why: We want the last place 2 appears

Step 5: Check index 3 -> value 2 matches target, check if last or move right

Array: [1, 2, 2, 2, 3, 4]
Index 3 is 2, check if next is different

Why: If next is not 2, this is last occurrence

Step 6: Check index 4 -> value 3 not equal to 2, so last occurrence is at index 3

Array: [1, 2, 2, 2, 3, 4]
Last 2 found at index 3

Why: Next value differs, so index 3 is last occurrence

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

Count of 2 in array is 3

Why: Number of occurrences is distance between first and last plus one

Result:

Array: [1, 2, 2, 2, 3, 4]
Occurrences of 2: 3

Annotated Code

DSA Javascript

class SortedArray {
  constructor(arr) {
    this.arr = arr;
  }

  findFirst(target) {
    let left = 0, right = this.arr.length - 1;
    let result = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (this.arr[mid] === target) {
        result = mid; // record current match
        right = mid - 1; // search left half for earlier occurrence
      } else if (this.arr[mid] < target) {
        left = mid + 1; // move right to find target
      } else {
        right = mid - 1; // move left
      }
    }
    return result;
  }

  findLast(target) {
    let left = 0, right = this.arr.length - 1;
    let result = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (this.arr[mid] === target) {
        result = mid; // record current match
        left = mid + 1; // search right half for later occurrence
      } else if (this.arr[mid] < target) {
        left = mid + 1; // move right
      } else {
        right = mid - 1; // move left
      }
    }
    return result;
  }

  countOccurrences(target) {
    const first = this.findFirst(target);
    if (first === -1) return 0; // target not found
    const last = this.findLast(target);
    return last - first + 1;
  }
}

// Driver code
const arr = [1, 2, 2, 2, 3, 4];
const target = 2;
const sortedArray = new SortedArray(arr);
const count = sortedArray.countOccurrences(target);
console.log(`Occurrences of ${target}: ${count}`);

if (this.arr[mid] === target) { result = mid; // record current match right = mid - 1; // search left half for earlier occurrence }

record first occurrence and continue searching left to find earliest index

if (this.arr[mid] === target) { result = mid; // record current match left = mid + 1; // search right half for later occurrence }

record last occurrence and continue searching right to find latest index

if (first === -1) return 0; // target not found

handle case when target is not in array

return last - first + 1;

calculate total count from first and last positions

Output

Occurrences 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 method is faster by using sorted order to jump quickly

Edge Cases

target not in array

countOccurrences returns 0 because findFirst returns -1

DSA Javascript

if (first === -1) return 0; // target not found

array is empty

countOccurrences returns 0 because findFirst returns -1 immediately

DSA Javascript

if (first === -1) return 0; // target not found

all elements are target

countOccurrences returns length of array as first is 0 and last is last index

DSA Javascript

return last - first + 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 fast counting.

Common Mistakes

Mistake: Stopping binary search when first match is found instead of continuing to find earliest occurrence
Fix: After finding a match, continue searching left half to find first occurrence

Mistake: Calculating count as last - first without adding 1
Fix: Add 1 to include both first and last positions in count

Summary

Counts how many times a target appears in a sorted array by finding first and last positions.

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

The key insight is that duplicates are grouped together, so finding boundaries gives the count.