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

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a sorted array of integers and a target number x, your task is to count how many times the number x appears in the array.

  • If the number is not found in the array, return 0.
  • All elements in the array are sorted in non-decreasing order.
  • You must use an efficient approach using binary search to find the count.

Examples❯

Input Array Key (x) Count Description
[1, 2, 2, 2, 3, 4] 2 3 2 appears at indices 1, 2, 3
[1, 1, 1, 1, 1] 1 5 All elements are the key
[5, 10, 10, 10, 20] 10 3 10 appears three times in the middle
[1, 2, 3, 4, 5] 6 0 6 is not present in the array
[1, 2, 3, 4, 5] 0 0 0 is not present and is smaller than all elements
[2] 2 1 Single element match
[2] 3 0 Single element, but not a match
[] 1 0 Empty array, so count is 0

Solution❯

Understanding the Problem

We are given a sorted array and a number x. Our task is to count how many times x appears in that array.

Since the array is already sorted, we can make use of binary search to efficiently find the count, instead of scanning the entire array.

How We'll Solve It

We will solve this in three main steps:

  1. Use binary search to find the first occurrence of x.
  2. Use binary search again to find the last occurrence of x.
  3. If x is found, compute the count as lastIndex - firstIndex + 1. Otherwise, return 0.

Example: Let's Understand with an Example

Consider the array [2, 4, 4, 4, 6, 8] and x = 4.

  • First occurrence of 4 is at index 1.
  • Last occurrence of 4 is at index 3.
  • So the count is 3 - 1 + 1 = 3.

What About Edge Cases?

  • Element appears only once:
    Array = [1, 2, 3, 4, 5], x = 3. First and last occurrence both at index 2 → count = 1.
  • Element doesn't exist:
    Array = [1, 2, 4, 5], x = 3. Binary search returns -1 → count = 0.
  • Element at the beginning:
    Array = [2, 2, 3, 4], x = 2. First at 0, last at 1 → count = 2.
  • Element at the end:
    Array = [1, 2, 3, 4, 4], x = 4. First at 3, last at 4 → count = 2.
  • Empty array:
    Array = [], any value of x → count = 0.

Why Use Binary Search?

Because the array is sorted, binary search lets us locate the first and last occurrences in O(log n) time.

If we used a regular linear scan, it would take O(n) time, which is much slower for large arrays.

Finally

This solution is efficient and elegant. By simply applying binary search twice, we can handle all normal and edge cases with minimal extra code.

It’s especially beginner-friendly because the logic is easy to break down: find first, find last, subtract the indices — and you’re done!

Algorithm Steps❯

  1. Use binary search to find the first occurrence of the key.
  2. Use binary search again to find the last occurrence of the key.
  3. If key is not found, return 0.
  4. Otherwise, return lastIndex - firstIndex + 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findFirst(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            end = mid - 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int findLast(int arr[], int n, int key) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            start = mid + 1;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
}

int countOccurrences(int arr[], int n, int key) {
    int first = findFirst(arr, n, key);
    int last = findLast(arr, n, key);
    if (first == -1) return 0;
    return last - first + 1;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 2;
    printf("Count of %d: %d\n", key, countOccurrences(arr, n, key));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If both first and last occurrences are found on the first try.
Average CaseO(log n)Binary search splits the array in half on each step, giving logarithmic performance.
Worst CaseO(log n)Both first and last searches may take log n steps independently.

Space Complexity❯

O(1)

Explanation: Only a few variables are used; no extra space is needed.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...