☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Count Occurrences in a Sorted Array

Easy TUF ID 229 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr sorted in non-decreasing order and an integer x. Return how many times x appears in arr. Return 0 when it does not appear at all. The expected running time is O(log n).

Constraints: 0 ≤ n ≤ 10^5, values and x fit in a 32-bit signed integer.

Example 1

arr = [2, 2, 3, 3, 3, 3, 4], x = 3
answer = 4                // indices 2..5 hold 3

Example 2

arr = [2, 2, 3, 3, 3, 3, 4], x = 5
answer = 0                // 5 is absent

Example 3

arr = [7, 7, 7, 7, 7], x = 7
answer = 5                // every element matches

Because the array is sorted, all copies of x are adjacent. Counting them is therefore the same as locating the two ends of that run and measuring its length, which turns a counting problem into a searching problem.

Approach 1: Brute force, count in one pass

Intuition. Look at every element and count the matches. Sorting is not used at all, which is why this is the baseline and not the answer.

Algorithm.

  1. count = 0.
  2. For each value v: if v == x, increment count.
  3. Return count.
static int bruteForce(int[] arr, int x) {
    int count = 0;
    for (int v : arr) {
        if (v == x) count++;
    }
    return count;
}

Complexity. Time O(n), space O(1). A linear scan is also what you would need if the array were not sorted, so this is the floor for unsorted data, but far from the floor here.

Approach 2: Optimal, first and last occurrence

Intuition. Since all copies of x are contiguous, the count is last - first + 1, where first and last are the indices of the first and last copies. Each of those is a binary search: run the ordinary search, but on a hit do not stop, record the index and keep going left (for first) or right (for last). If the first-occurrence search returns -1, x is absent and the count is 0, so we can skip the second search.

Algorithm.

  1. first = firstOccurrence(arr, x). If it is -1, return 0.
  2. last = lastOccurrence(arr, x).
  3. Return last - first + 1.
static int optimal(int[] arr, int x) {
    int first = firstOccurrence(arr, x);
    if (first == -1) return 0;                       // not present at all
    return lastOccurrence(arr, x) - first + 1;
}

private static int firstOccurrence(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) {
            ans = mid;            // found one; keep looking for an earlier copy
            hi = mid - 1;
        } else if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

private static int lastOccurrence(int[] arr, int x) {
    int lo = 0, hi = arr.length - 1, ans = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) {
            ans = mid;            // found one; keep looking for a later copy
            lo = mid + 1;
        } else if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

Dry run of firstOccurrence on arr = [2, 2, 3, 3, 3, 3, 4], x = 3:

lo hi mid arr[mid] comparison action
0 6 3 3 equal ans = 3, hi = 2
0 2 1 2 2 < 3 lo = 2
2 2 2 3 equal ans = 2, hi = 1
2 1     lo > hi return 2

lastOccurrence mirrors this and returns 5. Count = 5 - 2 + 1 = 4.

Complexity. Time O(log n): two binary searches of at most log2(n) + 1 steps each. Space O(1).

Why is continuing after a hit safe? For firstOccurrence, after arr[mid] == x we discard [mid, hi]. Everything there is >= x, so no copy of x before mid was discarded, and ans already remembers a valid copy. The final ans is therefore the leftmost copy.

Approach 3: Optimal, upper bound minus lower bound

Intuition. Define lowerBound(x) as the first index with arr[i] >= x and upperBound(x) as the first index with arr[i] > x, both returning n when nothing qualifies. Every copy of x sits at an index i with lowerBound <= i < upperBound, and every index in that half-open range holds a copy of x (values there are >= x and <= x). So the count is simply upperBound(x) - lowerBound(x).

The elegant part is that absence needs no special case: if x is not present the two bounds coincide and the difference is 0. This also works when x is larger than every element (both bounds are n) and when it is smaller than every element (both are 0).

Algorithm.

  1. Compute lb = lowerBound(arr, x) with the half-open template (hi = mid on arr[mid] >= x, else lo = mid + 1).
  2. Compute ub = upperBound(arr, x) the same way with arr[mid] > x.
  3. Return ub - lb.
static int optimalBounds(int[] arr, int x) {
    return upperBound(arr, x) - lowerBound(arr, x);
}

private static int lowerBound(int[] arr, int x) {     // first index with arr[i] >= x, or n
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private static int upperBound(int[] arr, int x) {     // first index with arr[i] > x, or n
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Complexity. Time O(log n), space O(1).

For Example 1, lowerBound(3) = 2 and upperBound(3) = 6, so the count is 6 - 2 = 4. For Example 2, both bounds are 7 = n and the count is 0.

Which optimal version to prefer? They cost the same. Approach 2 is easier to derive on the spot from the basic binary search. Approach 3 is shorter and more robust because it has no -1 sentinel to forget, and lower/upper bound are reusable in many other problems, so it is the version worth memorising.

Edge cases and pitfalls