In a sorted array with repeated values, count the occurrences of a key in O(log n) — without scanning the run of equal values.
Write CountOccurrences with a recursive lowerBound(a, key, low, high) that returns the index of the first element ≥ key in a[low..high−1] (or high if there is none), counting one probe per element examined. Then count = lowerBound(key + 1) − lowerBound(key). Read n, the n sorted values, and keys until the end of input.
For the input
10
1 3 3 3 5 5 8 8 8 8
3 8 4 1 9
the program prints
3: 3 time(s), indexes 1..3 (8 probes)
8: 4 time(s), indexes 6..9 (7 probes)
4: absent, would be inserted at index 4 (8 probes)
1: 1 time(s), indexes 0..0 (8 probes)
9: absent, would be inserted at index 10 (6 probes)