Count in a sorted list

In a sorted list of whole numbers, every copy of a value sits together in one block. You can count them without walking the whole list by finding the two edges of the block.

First, a helper: first_at_least(nums, value) returns the first position whose value is at least value, or the length of the list if there is none. It works like this. Keep low and high as the range of candidate positions, with high starting one past the end. While low < high, look at the middle position. If the value there is at least value, the answer is at the middle or to its left, so set high = mid. Otherwise it must be to the right, so set low = mid + 1. When the loop ends, low is the answer.

Now the count: first_at_least(nums, target) is where the block starts, and first_at_least(nums, target + 1) is where it ends, so the count is the difference. Write count_sorted(sorted_nums, target) that returns how many times target appears. The point is to practise the search rather than call count.

count_sorted([1, 2, 2, 2, 3, 5], 2)  ->  3
count_sorted([1, 3], 2)              ->  0

def count_sorted(sorted_nums, target):
    ...