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