Count distinct values in a sorted array

Count the distinct values in a sorted array of length n that holds only k distinct values, where k is much smaller than n. A linear scan works; do better by jumping over each run of equal values with binary search, in about O(k log n), and explain when that wins.