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:
- Use first occurrence search to find the leftmost index where the target appears
- Use last occurrence search to find the rightmost index where the target appears
- If the value exists, count =
(last_index - first_index + 1) - 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.