DSA sheet · Binary Search · Lower & upper bound pattern

Count Occurrences in a Sorted Array

Counting how many times a number appears sounds like a one-line loop, and it is. The teacher's point is that the question says the array is sorted, and every extra fact in a question is there for a reason. Sorted means binary search, and binary search means O(log n) instead of O(n). The trick: all copies of the target sit next to each other, so if we know where the block starts and where it ends, its length is the count. Finding the start and end is exactly the previous problem (First & Last Position).

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (incl. lower vs upper bound)
• Part A · Brute force: walk and count
• Part B · Optimal: first + last with binary search
• Part C · Her other style: keep mid in range (right = mid / left = mid)
• Part D · One line with lower_bound / upper_bound
• Part E · Revision page

Part 0 · Before starting

Why binary search works on a sorted array

Look at the middle value. If it's smaller than the target, everything on its left is even smaller, so that whole half can't contain the target and is thrown away. If it's bigger, the right half goes. Each look cuts the search area in half.

The yes/no view: for target 2 in [1, 1, 2, 2, 2, 2, 3], ask "is arr[i] >= 2?" The answers are no no yes yes yes yes yes. In a sorted array they switch only once, and binary search finds that switch point fast.

left, right, mid

• left (low) and right (high): the search area is every index from left to right, both included.
• mid: the middle index of that area. We only read arr[mid] each step.
• We never delete elements. "Throw away a half" means moving left to mid + 1 or right to mid - 1.
• Loop while left <= right: when they are equal, one cell is still unchecked. We stop only when they cross.

Why mid = left + (right - left) // 2?

In Java/C++, left + right can go past the biggest int (about 2.1 × 10⁹) and wrap to a negative number: that's overflow. left + (right - left) // 2 gives the same middle without ever making a number bigger than right. Python integers never overflow, so here it's just a good habit, and the teacher always uses it.

Lower bound vs upper bound, and why counting is just their difference

• Lower bound of x = first index whose value is ≥ x (n if none).
• Upper bound of x = first index whose value is > x (n if none).

For arr = [1, 1, 2, 2, 2, 2, 3] and x = 2:

  index:  0  1  2  3  4  5  6
  value:  1  1 [2  2  2  2] 3
                ^           ^
     lower bound = 2        upper bound = 6
     (first 2)              (first value after the 2s)

  first = LB = 2,  last = UB - 1 = 5
  count = last - first + 1 = 5 - 2 + 1 = 4
        = UB - LB             = 6 - 2     = 4

For a missing value like x = 0, both bounds land on index 0, so UB − LB = 0.

Part A · Brute force: walk and count

GeeksforGeeks · Number of occurrence

1The question in simple words

You get a sorted array arr and a number target. Return how many times the target appears. If it doesn't appear, return 0.

• [1, 1, 2, 2, 2, 2, 3], target 4 → 0 (not there).
• [8, 9, 10, 12, 12, 12], target 12 → 3.

2What the constraints tell us

• Array size from 1 up to 10⁶. So the array is never empty, but it can be big.
• Each value and the target are between 1 and 10⁶: all positive, and far below the ~2 × 10⁹ int limit.
• The teacher's reading: no piece of a constraint is there "just like that". 10⁶ elements × one pass = 10⁶ operations, well under the ~10⁸ that causes TLE (Time Limit Exceeded). So the linear solution will be accepted. But binary search does it in about 20 steps, so that's what the interviewer will push for.
• The values are small, but we still use the safe mid formula out of habit (see Part 0).

3Intuition

Walk through the array with a counter. Every time you see the target, add 1. The teacher mentions two easy ways: a simple count variable, or putting every number into a hash map (dictionary) of number → frequency and reading the target's entry.

4Building the logic

There's nothing tricky here. The real lesson is the question she asks right after: if the array is sorted and I scan it linearly anyway, what was the point of telling me it's sorted? A linear scan works on any array, sorted or not. When a question hands you a sorted array, the interviewer expects you to use that fact.

5Approach steps

1. count = 0.
2. For each value: if it equals the target, count += 1. If it's bigger, stop.
3. Return count.

6Code (Python)

class Solution:
    def countFreq(self, arr, target):
        count = 0
        for x in arr:
            if x == target:
                count += 1
            elif x > target:      # sorted: no more copies after this
                break
        return count

The hash-map version is collections.Counter(arr)[target]. It's also O(n), and it uses O(n) extra space.

7Code line by line

8Dry run

Answer 4.

9Complexity & remember

• Time O(n): one pass in the worst case. Space O(1) (O(n) for the hash map).

Part B · Optimal: first + last with binary search

1The question

Same question: count the target in a sorted array, but in O(log n).

2Constraints

n up to 10⁶ → log₂(10⁶) ≈ 20 steps per binary search. No empty array, so right = n - 1 is always a real index.

3Intuition: the copies form one block

Because the array is sorted, all copies of the target sit side by side in one block. If you know the index where the block starts (the first occurrence) and where it ends (the last occurrence), the count is the block's length:

  index:  0  1  2  3  4  5  6
  value:  1  1 [2  2  2  2] 3
                ^        ^
             first=2   last=5      length = 5 - 2 + 1 = 4

Finding the first and last occurrence with binary search is exactly the previous problem. The teacher says to watch that video first if you haven't, and here she only reuses the code. These notes recap it fully, so this page stands alone.

4Building the conditions from examples

Her example: [1, 1, 2, 2, 2, 2, 3], target 2. left = 0, right = 6, so mid = 3, and arr[3] = 2, a match. There are three cases to handle:

Case 1: arr[mid] == target

• For the first occurrence: the block might start earlier, so we go left. Save ans = mid first, then right = mid - 1.
• For the last occurrence: the block might end later, so we go right. Save ans = mid first, then left = mid + 1.

Why save before moving? If the side we move into has no more 2's, we haven't lost this one. It's already in ans.

Case 2: arr[mid] < target (e.g. mid lands on a 1)

1 is too small, and so is everything left of it. The 2's are on the right, so left = mid + 1. Why not left = mid? Because mid is a 1. It can never be counted, so there's no reason to keep it.

Case 3: arr[mid] > target (e.g. mid lands on a 3)

3 is too big. The 2's are on the left, so right = mid - 1. Mid is a 3, so we don't keep it either.

5Approach steps

1. first = binary search that, on a match, saves and goes left.
2. If first == -1 → the target is absent → return 0.
3. last = binary search that, on a match, saves and goes right.
4. Return last - first + 1.

6Code (Python)

class Solution:
    def countFreq(self, arr, target):
        first = self.findFirst(arr, target)
        if first == -1:                 # target not present
            return 0
        last = self.findLast(arr, target)
        return last - first + 1         # length of the block

    def findFirst(self, arr, target):
        left, right = 0, len(arr) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] == target:
                ans = mid
                right = mid - 1         # block may start earlier: go left
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

    def findLast(self, arr, target):
        left, right = 0, len(arr) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] == target:
                ans = mid
                left = mid + 1          # block may end later: go right
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

7Code line by line

8Dry run (hand tables)

arr = [1, 1, 2, 2, 2, 2, 3], target 2.

findFirst

findLast

count = 5 − 2 + 1 = 4 ✓. Target 4 on the same array: findFirst never matches → −1 → return 0.

9Complexity & remember

• Time: log n (first) + log n (last) + O(1) (the subtraction) = 2 log n = O(log n). For 10⁶ elements that's about 40 steps instead of a million.
• Space O(1).

Part C · Her other style: keep mid in range

1What she says

In this video the teacher also describes another way to handle a match. Instead of saving mid and jumping past it, keep mid inside the search area: right = mid for the first occurrence, left = mid for the last. Her reason: we don't know if another 2 exists beyond mid, so we must not jump over this one. Both styles are valid. Her final code uses the "save in ans" style from Part B.

2Constraints

Same. The array is non-empty, so arr[left] is always safe at the end.

3Intuition

If mid is never thrown away, the pointers squeeze toward it. The loop must then be while left < right (stop when they meet). With <=, right = mid could repeat forever on the same single cell. When they meet, that cell is the candidate. Check it once at the end.

4The trap: left = mid needs the UPPER middle

5Approach steps

1. First: while left < right, lower mid; if arr[mid] < target → left = mid + 1, else right = mid.
2. Last: while left < right, upper mid; if arr[mid] > target → right = mid - 1, else left = mid.
3. If arr[first] != target → return 0, else return last - first + 1.

6Code (Python)

class Solution:
    def countFreq(self, arr, target):
        left, right = 0, len(arr) - 1
        while left < right:                       # first occurrence
            mid = left + (right - left) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid                       # mid might be the first: keep it
        if arr[left] != target:
            return 0
        first = left

        right = len(arr) - 1                      # last occurrence (left = first is fine)
        while left < right:
            mid = left + (right - left + 1) // 2  # round UP because of left = mid
            if arr[mid] > target:
                right = mid - 1
            else:
                left = mid                        # mid might be the last: keep it
        return left - first + 1

7Line by line (only the new parts)

8Dry run on [1, 1, 2, 2, 2, 2, 3], target 2

5 − 2 + 1 = 4 ✓.

9Complexity & remember

O(log n) time, O(1) space. Starting the second search from left = first is a tiny speed-up. Starting from 0 also works.

Part D · One line with lower_bound / upper_bound

Not shown in the video. This is added to tie the code to the pattern's name.

From Part 0: count = upper bound − lower bound. If the target is missing, both bounds land on the same index, and the answer is 0 automatically. No −1 special case needed.

def lower_bound(arr, x):           # first index with arr[i] >= x
    left, right = 0, len(arr)      # note: right = n, half-open range [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] >= x:
            right = mid
        else:
            left = mid + 1
    return left

def upper_bound(arr, x):           # first index with arr[i] > x
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] > x:
            right = mid
        else:
            left = mid + 1
    return left

def count_freq(arr, target):
    return upper_bound(arr, target) - lower_bound(arr, target)

The two bound functions differ only in >= vs >. In Python, bisect.bisect_right(arr, t) - bisect.bisect_left(arr, t) gives the same count, which is useful for checking your own code.

Here right starts at n (one past the end) because the bound can be n. The range is "left included, right excluded", so the loop is left < right and right = mid is safe (mid rounds down, so it always shrinks the range).

Part E · Revision page

s = Solution()
print(s.countFreq([1, 1, 2, 2, 2, 2, 3], 2))   # 4
print(s.countFreq([1, 1, 2, 2, 2, 2, 3], 4))   # 0
print(s.countFreq([8, 9, 10, 12, 12, 12], 12)) # 3
print(s.countFreq([5], 5))                     # 1
print(s.countFreq([7, 7], 7))                  # 2

Based on this video: Count Occurrences in a Sorted Array