# Count number of occurrences (or frequency) in a sorted array

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)

Examples:

``````  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 3
Output: 1

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 1
Output: 2

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 4
Output: -1 // 4 doesn't occur in arr[]
``````

**Thoughts:

1. **Use conditional binary search to find the first and last occurrence of the target number. Then the length is right - left + 1

Code

``````class Solution:

def number_of_occurance(self, arr, k):
def first(arr, k):
low, high  = 0 , len(arr) -1
while (low <= high):
mid = low + (high - low >> 1)
if arr[mid] == k and (mid == 0 or k > arr[mid - 1]):
return mid
elif arr[mid] < k:
low = mid + 1
else:
high = mid - 1
return -1

def last(arr, low, high, k):
while ( low <= high):
mid = low + ((high - low)>> 1)
if arr[mid]==k and (mid == (len(arr) - 1) or k < arr[mid + 1]):
return mid
elif arr[mid] > k:
high = mid - 1
else:
low = mid + 1
return -1

i = first(arr, k)
if i < 0:
return -1
j = last(arr, i, len(arr) - 1, k)
return j - i + 1
arr = [1,1,2,2,2,2,3]
s = Solution()
print(s.number_of_occurance(arr,4))
``````

Full Explanation on GeeksforGeeks