Count Occurrences in Sorted Array - Binary Search (C++)

editorial
1

Problem: Count how many times x appears in sorted array.

Approach: Find first and last occurrence, then count = last - first + 1

Code (C++):
int countOccurrences(vector& nums, int x) {
int f = first(nums, x);
if (f == -1) return 0;
return last(nums, x) - f + 1;
}

Example:
nums = [2,4,4,4,6,8], x = 4
Count = 3 (index 1 to 3)

Time: O(log n) | Space: O(1)

1 Like