Problem

Given a sorted array of integers and a target element. Find the number of occurrences of the target in the array. You must write an algorithm with O(log n) runtime complexity.

Examples

Example 1:

1
2
3

Input: nums = [1, 1, 2, 2, 2, 2, 3],  target = 2
Output: 4
Explanation: 2 appears four times in the array

Example 2:

1
2
3

Input: a[] = {1, 1, 2, 2, 2, 2, 3},  target = 1
Output: 2
Explanation: 1 appears twice in the array

Example 3:

1
2
3

Input: a[] = {1, 1, 2, 2, 2, 2, 3},  target = 4
Output: 0
Explanation: 4 is not found in the array

Solution

Method 1 - Binary Search

This problem is a variation of the problem Find first and last positions of target element in sorted array. If we can find the first and last position of the target element in the array, then we can easily find the count which will be equal to lastPosition - firstPosition + 1

Code

1
2
3
4
5
6
7
8
9

static int count(int[] nums, target){
	int firstPosition = binarySearchFirstPosition(nums, target);
	int lastPosition = binarySearchLastPosition(nums, target);

	if(firstPosition != -1 && lastPosition != -1) {
		return lastPosition-firstPosition+1;
	}
	return 0;
}

Complexity

  • ⏰ Time complexity: O(log n) where n is number of elements in the array
  • 🧺 Space complexity: O(1)