To count how many times a number x
appears in a sorted array, we use a technique based on binary search. The idea is to find the first and last positions where x
appears, and then compute the total count from those two indices.
Understanding the Different Cases
Case 1: The element exists multiple times
If the key appears several times (for example, at indices 3, 4, 5), the total count is just lastIndex - firstIndex + 1
. Binary search helps us find both boundaries efficiently.
Case 2: The element appears only once
If the key is found at a single index (say, index 2), then both first and last index will be the same, so the count is 1.
Case 3: The element does not exist
If binary search doesn’t find the key at all, we simply return 0
because there are no occurrences in the array.
Case 4: Edge elements
Sometimes the element may be at the beginning or end of the array. For example, in [5, 6, 6, 6]
, key = 5 will be found only once at index 0. In [1, 2, 3, 4, 4]
, key = 4 appears at the end.
Case 5: Empty array
If the array has no elements, then the answer is obviously 0 because there's nothing to count.
Why Use Binary Search?
Since the array is sorted, binary search lets us quickly locate the first and last positions of the key. This reduces the time complexity from O(n) (checking every element) to O(log n), which is much faster, especially for large arrays.
In summary, we apply binary search twice — once to find the first occurrence and once for the last. If both searches return valid indices, we compute the total count. If not, we return 0. This makes the approach both efficient and elegant.