Binary SearchEasyO(log n) time · O(1) space

Count Number of Occurrences

Mahabharata — The Clan Census — Counting How Many Warriors Share the Same Name

एकस्य नाम्नः योधाः कति?। सत्वरं गणय। प्रथमं च अन्तिमं ज्ञात्वा — अन्तरं तत् संख्या॥

*How many warriors share one name? Count quickly. Find the first and last — their difference is the count.*

The Story

Given a sorted array, count the number of occurrences of a target value.

For `arr = [1,1,2,2,2,3]`, target=2: answer is 3.

This is a direct application of bs-3 (First and Last Position): - Find first occurrence index (lower bound of target) - Find last occurrence index (upper bound of target - 1) - Count = last - first + 1

Or elegantly using the `upperBound` and `lowerBound` functions: - `lowerBound(x)` = first index where arr[i] >= x - `upperBound(x)` = first index where arr[i] > x - Count = upperBound(x) - lowerBound(x)

For `[1,1,2,2,2,3]`, target=2: - lowerBound(2) = 2 (first index with value >= 2) - upperBound(2) = 5 (first index with value > 2) - Count = 5 - 2 = 3 ✓

```java int count(int[] arr, int n, int x) { return upperBound(arr, x) - lowerBound(arr, x); }

int lowerBound(int[] arr, int x) { int lo=0, hi=arr.length, res=arr.length; while (lo < hi) { int mid = (lo+hi)/2; if (arr[mid] >= x) { res=mid; hi=mid; } else lo=mid+1; } return res; }

int upperBound(int[] arr, int x) { int lo=0, hi=arr.length, res=arr.length; while (lo < hi) { int mid = (lo+hi)/2; if (arr[mid] > x) { res=mid; hi=mid; } else lo=mid+1; } return res; } ```

Yudhishthira needed to know how many soldiers in each clan. The answer required no linear scan — two binary searches gave it in O(log n).

The Linear Counter

Scan from left, count occurrences of target. O(n).

java

int countBruteForce(int[] arr, int n, int x) {
    int count = 0;
    for (int v : arr) if (v == x) count++;
    return count;
}

The Upper-Minus-Lower Wisdom

count = upperBound(x) - lowerBound(x). lowerBound = first index >= x; upperBound = first index > x. Two binary searches, each O(log n).

java

int count(int[] arr, int n, int x) {
    int lo = lowerBound(arr, x), hi = upperBound(arr, x);
    return hi - lo;
}

int lowerBound(int[] arr, int x) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int upperBound(int[] arr, int x) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > x) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Step-by-Step Walkthrough

[5,5,5], x=5
lowerBound: all >=5, converges to 0
upperBound: all not >5, lo goes to 3
Count = 3-0 = 3 ✅

Deep Insight

**lowerBound vs upperBound boundary condition:** - lowerBound: `arr[mid] >= x` → include mid, tighten from right (hi=mid) - upperBound: `arr[mid] > x` → include mid, tighten from right (hi=mid) The only difference is `>=` vs `>` in the condition.

**If x not present:** lowerBound and upperBound both point to the same index where x would be inserted → count = 0. Correct!

**Loop bound is `arr.length`** (not `arr.length-1`): This ensures we can return an index equal to arr.length (meaning 'past the end'), which handles the case where all elements are less than x.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Linear scan
Optimal	O(log n)	O(1)	Two binary searches

Pattern Recognition

✅ Count occurrences = upperBound - lowerBound
✅ lowerBound: >=x, hi=mid
✅ upperBound: >x, hi=mid
✅ If count=0, target not in array

**LeetCode Trigger Phrases:**
→ "count occurrences in sorted array"
→ "frequency of element in sorted array"

Bhagavad Gita 2.3

क्लैब्यं मा स्म गमः पार्थ नैतत्त्वय्युपपद्यते। क्षुद्रं हृदयदौर्बल्यं त्यक्त्वोत्तिष्ठ परन्तप॥

Do not yield to impotence, O Partha. It does not befit you. Shake off your faint-heartedness and arise, O scorcher of enemies.

Connection: The count is obtained not by laboriously scanning the entire army but by swiftly finding the boundaries of each clan. Like Krishna urging Arjuna to rise with strength rather than tediously doubting each warrior, binary search finds the answer with confident efficiency — two targeted strikes (lower and upper bound) reveal the full count without examining every element.