Exercise 4: Count Elements in Range

Your Task

Write a function count_in_range(nums, lo, hi) that counts how many elements in the sorted list nums fall within the inclusive range [lo, hi].

Your solution must run in O(log n) — no linear scan allowed.

---

Examples

nums = [1, 2, 4, 4, 5, 7, 8]

print(count_in_range(nums, 2, 5))   # 4  (values: 2, 4, 4, 5)
print(count_in_range(nums, 4, 4))   # 2  (both 4s)
print(count_in_range(nums, 6, 9))   # 2  (values: 7, 8)
print(count_in_range(nums, 0, 10))  # 7  (all elements)
print(count_in_range(nums, 9, 10))  # 0  (none)

---

Expected Complexity

	Complexity
Time	O(log n) — two binary searches
Space	O(1)

---

Approach

Use two binary search helpers:

• lower_bound(nums, val) — returns the first index where nums[index] >= val
• upper_bound(nums, val) — returns the first index where nums[index] > val

Then: count = upper_bound(nums, hi) - lower_bound(nums, lo)

---

Starter Code

def lower_bound(nums, val):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < val:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(nums, val):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= val:
            lo = mid + 1
        else:
            hi = mid
    return lo

def count_in_range(nums, lo, hi):
    pass

nums = [1, 2, 4, 4, 5, 7, 8]
print(count_in_range(nums, 2, 5))   # 4
print(count_in_range(nums, 4, 4))   # 2
print(count_in_range(nums, 6, 9))   # 2
print(count_in_range(nums, 0, 10))  # 7
print(count_in_range(nums, 9, 10))  # 0

---

Hints