Given a sorted array that can include duplicates find the number of times that a given number appears in the array.
The first thing that came to my mind was to do a binary search for the element and then check how many times it appears to the left and how many times it appears to the right. This has the drawback that if the array has a large number of appearances for that number then the performance might be greatly degraded because we would have to linearly search left and right.
To overcome this limitation we would need to do a custom binary search that searches for the first occurrence of a value and another that searches for the last element. Once we have those indexes we can find the difference and that is the number of appearances: