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!
Comments
Loading comments...