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.

OR

Given a sorted (ascending order) array of integers, find the number of occurrences of a given number x in the array.

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: nums = [1, 1, 2, 2, 2, 2, 3],  target = 1
Output: 2
Explanation: 1 appears twice in the array

Example 3:

1
2
3

Input: nums = [1, 1, 2, 2, 2, 2, 3],  target = 4
Output: 0
Explanation: 4 is not found in the array
Similar Problems

Solution

Method 1 – Binary Search for First and Last Position

Intuition

Since the array is sorted, we can use binary search to efficiently find the first and last positions of the target. This is the problem we have already solved - Find first and last positions of target element in sorted array .The number of occurrences is simply last - first + 1 if the target exists.

Approach

  1. Use binary search to find the first occurrence of the target.
  2. Use binary search to find the last occurrence of the target.
  3. If the target is not found, return 0.
  4. Otherwise, return last - first + 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
		int countOccurrences(const std::vector<int>& nums, int target) {
				int first = findFirst(nums, target);
				if (first == -1) return 0;
				int last = findLast(nums, target);
				return last - first + 1;
		}
private:
		int findFirst(const std::vector<int>& nums, int target) {
				int left = 0, right = nums.size() - 1, ans = -1;
				while (left <= right) {
						int mid = left + (right - left) / 2;
						if (nums[mid] < target) left = mid + 1;
						else if (nums[mid] > target) right = mid - 1;
						else {
								ans = mid;
								right = mid - 1;
						}
				}
				return ans;
		}
		int findLast(const std::vector<int>& nums, int target) {
				int left = 0, right = nums.size() - 1, ans = -1;
				while (left <= right) {
						int mid = left + (right - left) / 2;
						if (nums[mid] < target) left = mid + 1;
						else if (nums[mid] > target) right = mid - 1;
						else {
								ans = mid;
								left = mid + 1;
						}
				}
				return ans;
		}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func countOccurrences(nums []int, target int) int {
		first := findFirst(nums, target)
		if first == -1 {
				return 0
		}
		last := findLast(nums, target)
		return last - first + 1
}

func findFirst(nums []int, target int) int {
		left, right, ans := 0, len(nums)-1, -1
		for left <= right {
				mid := left + (right-left)/2
				if nums[mid] < target {
						left = mid + 1
				} else if nums[mid] > target {
						right = mid - 1
				} else {
						ans = mid
						right = mid - 1
				}
		}
		return ans
}

func findLast(nums []int, target int) int {
		left, right, ans := 0, len(nums)-1, -1
		for left <= right {
				mid := left + (right-left)/2
				if nums[mid] < target {
						left = mid + 1
				} else if nums[mid] > target {
						right = mid - 1
				} else {
						ans = mid
						left = mid + 1
				}
		}
		return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
		public int countOccurrences(int[] nums, int target) {
				int first = findFirst(nums, target);
				if (first == -1) return 0;
				int last = findLast(nums, target);
				return last - first + 1;
		}
		private int findFirst(int[] nums, int target) {
				int left = 0, right = nums.length - 1, ans = -1;
				while (left <= right) {
						int mid = left + (right - left) / 2;
						if (nums[mid] < target) left = mid + 1;
						else if (nums[mid] > target) right = mid - 1;
						else {
								ans = mid;
								right = mid - 1;
						}
				}
				return ans;
		}
		private int findLast(int[] nums, int target) {
				int left = 0, right = nums.length - 1, ans = -1;
				while (left <= right) {
						int mid = left + (right - left) / 2;
						if (nums[mid] < target) left = mid + 1;
						else if (nums[mid] > target) right = mid - 1;
						else {
								ans = mid;
								left = mid + 1;
						}
				}
				return ans;
		}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
		fun countOccurrences(nums: IntArray, target: Int): Int {
				val first = findFirst(nums, target)
				if (first == -1) return 0
				val last = findLast(nums, target)
				return last - first + 1
		}
		private fun findFirst(nums: IntArray, target: Int): Int {
				var left = 0; var right = nums.size - 1; var ans = -1
				while (left <= right) {
						val mid = left + (right - left) / 2
						when {
								nums[mid] < target -> left = mid + 1
								nums[mid] > target -> right = mid - 1
								else -> { ans = mid; right = mid - 1 }
						}
				}
				return ans
		}
		private fun findLast(nums: IntArray, target: Int): Int {
				var left = 0; var right = nums.size - 1; var ans = -1
				while (left <= right) {
						val mid = left + (right - left) / 2
						when {
								nums[mid] < target -> left = mid + 1
								nums[mid] > target -> right = mid - 1
								else -> { ans = mid; left = mid + 1 }
						}
				}
				return ans
		}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
		def count_occurrences(self, nums: list[int], target: int) -> int:
				def find_first(nums, target):
						left, right, ans = 0, len(nums) - 1, -1
						while left <= right:
								mid = (left + right) // 2
								if nums[mid] < target:
										left = mid + 1
								elif nums[mid] > target:
										right = mid - 1
								else:
										ans = mid
										right = mid - 1
						return ans
				def find_last(nums, target):
						left, right, ans = 0, len(nums) - 1, -1
						while left <= right:
								mid = (left + right) // 2
								if nums[mid] < target:
										left = mid + 1
								elif nums[mid] > target:
										right = mid - 1
								else:
										ans = mid
										left = mid + 1
						return ans
				first = find_first(nums, target)
				if first == -1:
						return 0
				last = find_last(nums, target)
				return last - first + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

impl Solution {
		pub fn count_occurrences(nums: &[i32], target: i32) -> i32 {
				fn find_first(nums: &[i32], target: i32) -> i32 {
						let (mut left, mut right, mut ans) = (0, nums.len() as i32 - 1, -1);
						while left <= right {
								let mid = left + (right - left) / 2;
								let mid_val = nums[mid as usize];
								if mid_val < target {
										left = mid + 1;
								} else if mid_val > target {
										right = mid - 1;
								} else {
										ans = mid;
										right = mid - 1;
								}
						}
						ans
				}
				fn find_last(nums: &[i32], target: i32) -> i32 {
						let (mut left, mut right, mut ans) = (0, nums.len() as i32 - 1, -1);
						while left <= right {
								let mid = left + (right - left) / 2;
								let mid_val = nums[mid as usize];
								if mid_val < target {
										left = mid + 1;
								} else if mid_val > target {
										right = mid - 1;
								} else {
										ans = mid;
										left = mid + 1;
								}
						}
						ans
				}
				let first = find_first(nums, target);
				if first == -1 {
						return 0;
				}
				let last = find_last(nums, target);
				(last - first + 1) as i32
		}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
		countOccurrences(nums: number[], target: number): number {
				function findFirst(nums: number[], target: number): number {
						let left = 0, right = nums.length - 1, ans = -1;
						while (left <= right) {
								const mid = left + Math.floor((right - left) / 2);
								if (nums[mid] < target) left = mid + 1;
								else if (nums[mid] > target) right = mid - 1;
								else { ans = mid; right = mid - 1; }
						}
						return ans;
				}
				function findLast(nums: number[], target: number): number {
						let left = 0, right = nums.length - 1, ans = -1;
						while (left <= right) {
								const mid = left + Math.floor((right - left) / 2);
								if (nums[mid] < target) left = mid + 1;
								else if (nums[mid] > target) right = mid - 1;
								else { ans = mid; left = mid + 1; }
						}
						return ans;
				}
				const first = findFirst(nums, target);
				if (first === -1) return 0;
				const last = findLast(nums, target);
				return last - first + 1;
		}
}

Complexity

  • ⏰ Time complexity: O(log n) — Each binary search runs in logarithmic time.
  • 🧺 Space complexity: O(1) — Only a constant number of variables are used.

Method 2 – Single Pass Binary Search (Lower Bound / Upper Bound)

Intuition

We can use two modified binary searches to find the leftmost index where nums[i] >= target and the rightmost index where nums[i] > target. The count is then right - left. This approach is similar to using lower_bound and upper_bound in C++ STL and can be implemented in one pass in some languages.

Approach

  1. Use binary search to find the leftmost index where nums[i] >= target (left).
  2. Use binary search to find the leftmost index where nums[i] > target (right).
  3. The count is right - left if left < len(nums) and nums[left] == target, else 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int countOccurrences(const std::vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        int right = lowerBound(nums, target + 1);
        if (left == nums.size() || nums[left] != target) return 0;
        return right - left;
    }
private:
    int lowerBound(const std::vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func countOccurrences(nums []int, target int) int {
    left := lowerBound(nums, target)
    right := lowerBound(nums, target+1)
    if left == len(nums) || nums[left] != target {
        return 0
    }
    return right - left
}

func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int countOccurrences(int[] nums, int target) {
        int left = lowerBound(nums, target);
        int right = lowerBound(nums, target + 1);
        if (left == nums.length || nums[left] != target) return 0;
        return right - left;
    }
    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countOccurrences(nums: IntArray, target: Int): Int {
        val left = lowerBound(nums, target)
        val right = lowerBound(nums, target + 1)
        if (left == nums.size || nums[left] != target) return 0
        return right - left
    }
    private fun lowerBound(nums: IntArray, target: Int): Int {
        var left = 0; var right = nums.size
        while (left < right) {
            val mid = left + (right - left) / 2
            if (nums[mid] < target) left = mid + 1
            else right = mid
        }
        return left
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def count_occurrences(self, nums: list[int], target: int) -> int:
        def lower_bound(nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left
        left = lower_bound(nums, target)
        right = lower_bound(nums, target + 1)
        if left == len(nums) or nums[left] != target:
            return 0
        return right - left
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn count_occurrences(nums: &[i32], target: i32) -> i32 {
        fn lower_bound(nums: &[i32], target: i32) -> usize {
            let (mut left, mut right) = (0, nums.len());
            while left < right {
                let mid = left + (right - left) / 2;
                if nums[mid] < target {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            left
        }
        let left = lower_bound(nums, target);
        let right = lower_bound(nums, target + 1);
        if left == nums.len() || nums[left] != target {
            return 0;
        }
        (right - left) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    countOccurrences(nums: number[], target: number): number {
        function lowerBound(nums: number[], target: number): number {
            let left = 0, right = nums.length;
            while (left < right) {
                const mid = left + Math.floor((right - left) / 2);
                if (nums[mid] < target) left = mid + 1;
                else right = mid;
            }
            return left;
        }
        const left = lowerBound(nums, target);
        const right = lowerBound(nums, target + 1);
        if (left === nums.length || nums[left] !== target) return 0;
        return right - left;
    }
}

Complexity

  • ⏰ Time complexity: O(log n) — Each binary search runs in logarithmic time.
  • 🧺 Space complexity: O(1) — Only a constant number of variables are used.