Data Structures and Algorithms (DSA)  

Count Occurrences of an Element in a Sorted Array (Using Binary Search)

Introduction

Counting how many times an element appears in a sorted array is a very common DSA interview question. Many beginners immediately think of scanning the entire array, which works but is not efficient.

In simple words, this problem asks you to find how many times a number is repeated in a sorted list.

This article explains how to solve this problem efficiently using Binary Search, in simple, human-friendly language, step by step.

Real-World Meaning of Counting Occurrences

Imagine a class attendance register where student names are written in sorted order. If a teacher asks:

  • How many times does the name “Rahul” appear?

You would not read the entire register line by line. Instead, you would find where “Rahul” starts and where it ends. The number of entries in between is the answer.

This is exactly how we solve this problem using binary search.

Problem Statement

You are given:

  • A sorted array of integers

  • A target value

Your task is to count how many times the target appears in the array.

Example

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

Output

Count = 3

Before vs After Understanding

Linear Scan (Before)

  • Check every element

  • Count matches

  • Works but slow for large arrays

Binary Search Approach (After)

  • Find first occurrence

  • Find last occurrence

  • Calculate count instantly

Why Binary Search Works Here

Because the array is sorted:

  • All occurrences of a number appear together

  • Once we know the start and end positions, counting is easy

This is why binary search is perfect for this problem.

What Interviewers Are Actually Testing

Interviewers want to check:

  • Do you know how to reuse binary search?

  • Can you solve frequency problems efficiently?

  • Do you understand boundary-based searching?

This question often follows “first and last occurrence”.

Key Idea (Very Simple)

  1. Find the first occurrence of the target

  2. Find the last occurrence of the target

  3. Use the formula:

Count = lastIndex - firstIndex + 1

If the element is not found, count is 0.

Step-by-Step Logic

  1. Use binary search to find first occurrence

  2. Use binary search to find last occurrence

  3. If first occurrence is -1, return 0

  4. Otherwise, calculate the count

Dry Run Example

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

  • First occurrence index = 1

  • Last occurrence index = 3

Count = 3 - 1 + 1 = 3

One-Line Logic Before Code

Count is the distance between first and last positions of the target.

Code Implementation (C++)

int firstOccurrence(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int lastOccurrence(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int countOccurrences(vector<int>& arr, int target) {
    int first = firstOccurrence(arr, target);
    if (first == -1) return 0;
    int last = lastOccurrence(arr, target);
    return last - first + 1;
}

Common Beginner Mistakes

  • Using linear search in interviews

  • Forgetting array must be sorted

  • Not handling element-not-found case

Time and Space Complexity

  • Time Complexity: O(log n)

  • Space Complexity: O(1)

This is far better than linear scanning.

Easy Summary (Explain Like I’m 10)

If the same number appears many times in a sorted list, binary search helps you quickly find where it starts and where it ends. The number of times it appears is just the number of positions in between.

Summary

Counting occurrences of an element in a sorted array can be done very efficiently using binary search. By finding the first and last positions of the target element and calculating the difference, you avoid unnecessary scanning and achieve logarithmic time complexity. This pattern is extremely useful in interviews and builds a strong foundation for solving frequency-based and boundary-search problems in DSA.

Membership not found