Finding nearest value in a sorted set

Question

I am interested in math notation of finding the nearest value in a sorted set of values to the given value.

3, 7, 10, 15, 20, 29, 48, 67, 94

If i want to find the nearest value to 23, it would be 20.

How to represent this using a math notation?

Answer 1

This is an excellent question, and I don't know why you're getting all this flak in the comments. However:

• The term "sorted set" doesn't really mean anything AFAIK. The important observation is that your set $\{3,7,\ldots,94\}$ is a subset of a metric space, namely $\mathbb{R}$. So, lets work at this higher level of generality.

• There's no standard notation for this stuff. Some terms to look up are "metric projection" and "Chebyshev set." But your particular set isn't a Chebyshev set, which complicates the analysis. Gory details follow.

Okay, here's the math:

Given a metric space $X$ and a subset $A$, there's a relation $\underline{A}:X \nrightarrow A$ defined as follows:

$$\underline{A}(x,a)\iff \forall b \in A(d(x,b) \geq d(x,a))$$

If $A$ is compact, then $\underline{A}$ is entire; use the extreme value theorem applied to the map $X \rightarrow \mathbb{R}$ defined by $x \mapsto d(x,A),$ where $d(x,A)$ is shorthand for $\min_{a \in A}d(x,a).$

Unfortunately, the relation $\underline{A}$ won't usually be deterministic: for example, if $A = \{0,1\}$ and $X=\mathbb{R}$ with the usual metric structure, then $(1/2,0) \in \underline{A}$ and $(1/2,1) \in \underline{A}$.

There's a few ways of treating this. One is to accept that $\underline{A}$ yields a subset of $X$, rather than an element. That is, we re-analyse $\underline{A} : X \nrightarrow A$ as $\underline{A} : X \rightarrow \mathcal{P}(A)$, where $\mathcal{P}$ is the powerset function. For example: $$\underline{A}(1/2) = \{0,1\}.$$

Another option is to choose a subfunction $X \rightarrow A.$ If $A$ is compact, then this is always possible, because, by the axiom of choice, every entire relation has a subfunction. However, in the special case $X=\mathbb{R}$, the axiom of choice isn't really necessary, because we can choose an explicit strategy for disambiguating the values of $\underline{A}$. For example, each of "round toward the negative direction"/"round toward the positive direction"/"round toward zero"/"round away from zero" will give you a subfunction.

For instance, suppose we want to round toward the negative direction. Mathematically, this means defining $f_A : X \rightarrow A$ by $$f_A(x) = \min \underline{A}(x).$$

For example, if we go back to $A =\{0,1\}$ and $X=\mathbb{R}$, we obtain $$f_A(1/2) = \min\{0,1\} = 0.$$