AlgoViz
HomeBinary Search

Count Occurrences in a Sorted Array

Easy

Last occurrence minus first, plus one

Problem

You are given a sorted array of integers arr and an integer target. Your task is to determine how many times target appears in arr. Return the count of occurrences of target in the array.

In simple words

Find the first and last spot of the value with two binary searches; subtract to get the count.

The idea

Binary search twice: once biased left to find the first index of the target and once biased right for the last. The count is the difference plus one, and both searches are O(log n) so the total stays logarithmic.

The trick

  • First occurrence: on a match, keep searching the left half. Last: keep searching the right.
  • Equivalently, lowerBound(x+1) - lowerBound(x).
  • Return 0 when the first search finds nothing.
1
2
2
2
3
0
1
2
3
4
target2

Step 1 of 7. Brute force: scan the whole array counting 2. Values: 1, 2, 2, 2, 3. target 2.

1/7
Brute force
timeO(n)spaceO(1)

Scan and count.

1// walk the whole array counting matches2for (let i = 0; i < n; i++)3  if (nums[i] === target) count++;4return count;

Input

array
[1, 2, 2, 2, 3]

Memory

i
—
target
2

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 2, 2, 3], target = 2
Output:
3
Explanation:
2 appears 3 times.

Example 2

Input:
nums = [1, 1, 2, 3], target = 1
Output:
2
Explanation:
1 appears twice.

Example 3

Input:
nums = [1, 2, 3], target = 5
Output:
0
Explanation:
5 is absent → 0.

Constraints

  • 1 <= arr.length <= 10^6
  • 1 <= arr[i] <= 10^6
  • 1 <= target <= 10^6

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.