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.

Practice

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

easy

A. It sorts the array automatically.

B. It reduces the search time from linear to logarithmic.

C. It counts all elements without searching.

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 faster than checking every element.

2. Step 2: Compare linear vs binary search

   Linear search checks each element one by one (O(n)), binary search works in O(log n) time.

3. Final Answer:

   It reduces the search time from linear to logarithmic. -> Option B

4. Quick Check:

   Binary search = faster search [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 of the following is the correct syntax to find the middle index in a binary search on array arr between indices low and high in JavaScript?

easy

A. const mid = low + high;

B. const mid = (low + high) / 2;

C. const mid = Math.ceil((low + high) / 2);

D. const mid = Math.floor((low + high) / 2);

Solution

1. Step 1: Calculate middle index correctly

   We use Math.floor to get the integer index because array indices must be whole numbers.

2. Step 2: Avoid floating point and wrong calculations

   Using just division or Math.ceil can cause errors or out-of-bound indices.

3. Final Answer:

   const mid = Math.floor((low + high) / 2); -> Option D

4. Quick Check:

   Use Math.floor for middle index [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Not using Math.floor causing float index
• Using Math.ceil which may skip elements
• Adding indices without division

3. What will be the output of the following JavaScript code?

function countOccurrences(arr, x) {
  let low = 0, high = arr.length - 1;
  let count = 0;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === x) {
      count++;
      let left = mid - 1;
      while (left >= 0 && arr[left] === x) {
        count++;
        left--;
      }
      let right = mid + 1;
      while (right < arr.length && arr[right] === x) {
        count++;
        right++;
      }
      break;
    } else if (arr[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return count;
}

console.log(countOccurrences([1,2,2,2,3,4,5], 2));

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Find one occurrence of 2 using binary search

   The binary search finds 2 at index 2 (middle of array).

2. Step 2: Count all adjacent 2s on left and right

   Left side: indices 1 and 0 checked; only index 1 has 2. Right side: index 3 has 2. Total count = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Count adjacent 2s = 3 [OK]

Hint: Count neighbors after binary search hit [OK]

Common Mistakes:

• Counting only the found element once
• Not checking neighbors on both sides
• Incorrect loop conditions causing infinite loops

4. The following code is intended to count occurrences of x in a sorted array arr. What is the bug?

function countOccurrences(arr, x) {
  let low = 0, high = arr.length - 1;
  let count = 0;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === x) {
      count++;
      let left = mid - 1;
      while (arr[left] === x) {
        count++;
        left--;
      }
      let right = mid + 1;
      while (arr[right] === x) {
        count++;
        right++;
      }
      break;
    } else if (arr[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return count;
}

medium

A. The while loops do not check array bounds before accessing elements.

B. The binary search condition is incorrect.

C. The count variable is not initialized.

D. The function does not return any value.

Solution

1. Step 1: Analyze while loops for boundary checks

   The loops check arr[left] === x and arr[right] === x without verifying if left or right are valid indices.

2. Step 2: Identify risk of out-of-bounds access

   If left becomes -1 or right exceeds array length, accessing arr[left] or arr[right] causes errors.

3. Final Answer:

   The while loops do not check array bounds before accessing elements. -> Option A

4. Quick Check:

   Always check array bounds before access [OK]

Hint: Check array bounds before accessing elements [OK]

Common Mistakes:

• Ignoring array index limits in loops
• Assuming array access is always safe
• Not breaking loop on invalid index

5. Given a sorted array arr = [1,2,2,2,3,3,4,5,5,5,5,6], which approach is the most efficient to count occurrences of 5 without scanning the entire array?

hard

A. Use binary search to find first and last positions of 5, then calculate count.

B. Use a for loop to count all 5s by scanning the whole array.

C. Sort the array again and count 5s.

D. Use a hash map to store counts of all elements.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so all 5s are grouped together.

2. Step 2: Use binary search to find boundaries

   Find the first index of 5 and last index of 5 using binary search, then count = last - first + 1.

3. Step 3: Compare efficiency

   This method is O(log n), faster than scanning entire array (O(n)) or sorting again (O(n log n)).

4. Final Answer:

   Use binary search to find first and last positions of 5, then calculate count. -> Option A

5. Quick Check:

   Binary search boundaries = efficient count [OK]

Hint: Find first and last index with binary search [OK]

Common Mistakes:

• Scanning entire array unnecessarily
• Sorting already sorted array again
• Using extra space with hash map when not needed