I can share logic which will optimize little bit to solve this problem,

Let me divide the problem in 2 parts.

Considering Total number of elements in array is N, and key element searching is NUM, suppose it exists k times in the array.

1> Search the number and it's position in a SORTED ARRAY.

2> And getting the count of number of times the number exists.

Part 1: - Apply binary search on it and get the index where it is the number exist for this complexity will be log(N)

Part 2:- Then after getting the index where the number present,

**Browse its left side till you get the same number**

**Browse its right side till you get the same number**

So complexity K + log(N) in best/average cases , in worst case K count can be N also for all the array element is same and equal to the number you are searching for.

Example

0 1 2 3 4 5 6 7 8 9 10 (Index)

3 3 4 **8 8 8 8** 12 14 18 45

N = 11

Key = 8 i am searching for it

K = 4 as 8 is present 4 times.

Part 1 : Using binary search we can find that 8 is present at **Index 5**

Part 2:

Then go linearly towards **Left side** of index 5, till you get different number so here count will be 2

Then go linearly towards **Right side** of index 5, till you get different number so here count will be 1

So total count = 1+ 2 +1 = 4

Hope it is clear.