Course contentsShow
← Computer Science
Lesson 814 of 2,87219. Searching and SelectionFree lesson

Counting Occurrences with Binary Search

Use first and last occurrence searches to count how many times a value appears in O(log n) time.

Counting Occurrences with Binary Search

What You'll Learn

You'll learn how to efficiently count how many times a value appears in a sorted array using binary search in O(log n) time.

The Core Idea

When you need to count occurrences of a value in a sorted array, you could scan the entire array in O(n) time. But there's a much smarter way: find where the value starts and where it ends, then subtract!

Think of it like finding how many pages discuss "binary search" in a textbook's index. The index tells you "pages 45-52" — you don't flip through every page; you just calculate: 52 - 45 + 1 = 8 pages.

How It Works

Since you've already learned to find the first occurrence and last occurrence of a value using binary search variants:

  1. Use first occurrence search to find the leftmost index where the target appears
  2. Use last occurrence search to find the rightmost index where the target appears
  3. If the value exists, count = (last_index - first_index + 1)
  4. If the value doesn't exist (first occurrence returns -1), count = 0

Example

For array [1, 2, 2, 2, 2, 3, 4] and target 2:

  • First occurrence: index 1
  • Last occurrence: index 4
  • Count: 4 - 1 + 1 = 4 occurrences

Time Complexity

Both first and last occurrence searches take O(log n), so the total time is O(log n) + O(log n) = O(log n) — much faster than the O(n) linear scan!

Key Takeaway: To count occurrences in a sorted array efficiently, find the first and last occurrence indices using binary search variants, then calculate the difference to get the count in O(log n) time.