Prerequisites: Find the First True in a Sorted Boolean Array , First and last occurrence of an Element in a Sorted Array
Question
Given a sorted array and a number target, write a function that counts the occurrences of an element in the array. The expected time complexity is O(logn)
nums = [1,2,4,4,4,6]
output = 3Think?
Hints: First and last occurrence of an Element in a Sorted Array
Does that help? We can find the number of occurrences of an element in a sorted array by subtracting the last index of the element from the first index. For example, in the array [1,2,4,4,4,6], element 4 has a first index of 2 and a last index of 4, so the number of occurrences is 3 (4 - 2 + 1). Simple as that!