Can you explain this improvement to this frequency distribution algorithm?

Question

I came across the following in a text book:

Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting. To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. By walking to the left of this point until the first the element is not k and then doing the same to the right, we can find this count in O(log n + c) time, where c is the number of occurrences of k. Even better, the number of instances of k can be found in O(log n) time by using binary search to look for the positions of both k − ε and k + ε (where ε is arbitrarily small) and then taking the difference of these positions.

The part I don't understand is the part I have emphasised in bold text - I can't understand how you might choose 'ε' and how you would know that the list even contains this 'ε'..

Answer 1

You don't really choose $\epsilon$. Rather, you (virtually) add $k-\epsilon$ and $k+\epsilon$ to your linear order at the correct spots, a feat which you accomplish by modifying your comparison function. Binary search requires you to answer queries of the form $x < y$. When looking for $k-\epsilon$ (or $k+\epsilon$), either $x$ or $y$ could be $k-\epsilon$ (or $k+\epsilon$), and so we have to extend the definition of the comparison function, as follows: $$ k-\epsilon < y \text{ if } k \leq y \\ x < k-\epsilon \text{ if } x < k \\ k+\epsilon < y \text{ if } k < y \\ x < k+\epsilon \text{ if } x \leq k $$ The comparison functions on the right are the original ones (with $x \leq y$ being shorthand for $x < y$ or $x = y$), and the ones on the left are the new ones.

Answer 2

The value of ε is a positive number that is smaller than difference of two possible values in the sequence. For example if you have a sequence of integer values, the value of ε is any number <1 but >0