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

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

Visualization Player

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:

Use binary search to find the first occurrence of x.
Use binary search again to find the last occurrence of x.
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❯

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

Code

Java

Python

JavaScript

C++

Kotlin

Swift

public class CountOccurrences {

  public static int countOccurrences(int[] arr, int key) {
    int first = findFirst(arr, key);
    int last = findLast(arr, key);

    if (first == -1 || last == -1) return 0;
    return last - first + 1;
  }

  private static int findFirst(int[] arr, int key) {
    int start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (arr[mid] == key) {
        res = mid;
        end = mid - 1; // go left to find earlier occurrence
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  private static int findLast(int[] arr, int key) {
    int start = 0, end = arr.length - 1, res = -1;
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (arr[mid] == key) {
        res = mid;
        start = mid + 1; // go right to find later occurrence
      } else if (arr[mid] < key) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] arr = {1, 2, 2, 2, 3, 4};
    int key = 2;
    System.out.println("Count of " + key + ": " + countOccurrences(arr, key));
  }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	If both first and last occurrences are found on the first try.
Average Case	O(log n)	Binary search splits the array in half on each step, giving logarithmic performance.
Worst Case	O(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.

⬅ Previous TopicLast Occurrence in a Sorted Array

Next Topic ⮕Search Element in a Rotated Sorted Array

Comments

Loading comments...