Nearest¶

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description¶

Nearest[list, x]

Gives the element of list closest to x, as a list. All elements tied at the minimum distance Abs[element - x] are returned, in their original order; an empty list gives {}. Returns unevaluated unless every distance is a real number, so a symbolic element or target leaves the expression unchanged rather than dropping it from the result.

Examples (6)¶

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (3)¶

In[1]:= Nearest[{1, 5, 10}, 3]
Out[1]= {1, 5}

In[2]:= Nearest[{10, 20, 30}, 100]
Out[2]= {30}

In[3]:= Nearest[{1, a, 3}, 2]
Out[3]= Nearest[{1, a, 3}, 2]

Applications (3)¶

The single closest element

In[4]:= Nearest[{1, 2, 3, 4, 5}, 2.3]
Out[4]= {2}

A tie returns both, in input order

In[5]:= Nearest[{10, 20, 30, 40}, 25]
Out[5]= {20, 30}

Complex elements compare by modulus

In[6]:= Nearest[{3 + 4 I, 1}, 0]
Out[6]= {1}

Algorithm¶

Nearest[list, x] -- the element(s) of list closest to the target x.

  Nearest[{1, 5, 10}, 3]    -> {1, 5}
  Nearest[{10, 20, 30}, 100] -> {30}
  Nearest[{}, 3]             -> {}

Distance is Abs[element - x], composed from the existing internal_subtract and internal_abs rather than a bespoke helper, so a complex element uses its modulus for free: Nearest[{3 + 4 I, 1}, 0] is {1} because the distances are 5 and 1.

ALL elements tied at the minimum distance are returned, in their original order. That requirement is what fixes the algorithm. The obvious neighbour, RankedMin (sort.c), selects with a quickselect whose comparator carries an original-index tiebreak (sort.c:932) existing precisely to make ties IMPOSSIBLE, so that exactly one element can win -- the opposite of what is needed here. The shape used instead is MinimalBy's (sort.c:663-716): one pass to find the minimum, a second to collect every distance equal to it. Input order among ties then falls out of the ascending collect pass, so there is no tie logic in this file at all.

Nearest diverges from MinimalBy in exactly one respect, and deliberately. Every distance must be a real number, or the whole call stays unevaluated. MinimalBy[{1, a, 3}, Abs[# - 2] &] answers {1, 3}: expr_compare orders symbols after all numbers (sort.c:379-380), so the symbolic element is never minimal and silently vanishes from a result that still looks plausible. Gating on the DISTANCE rather than on the element covers a symbolic element, a symbolic target, and a non-real complex in a single check. A symbolic real such as Pi is rejected too -- Abs[Pi - 3] stays as Abs[-3 + Pi] -- rather than being numericalized the way RankedMin's ranked_numeric_key would.

Cost: O(n) distance evaluations, O(n) comparisons, O(n) peak extra memory. The two evaluate passes per element dominate, so this is an interpreter-speed path and not a buffer path. There is no exact-hit short circuit: a later element can tie at distance 0, and dropping it would break the tie contract.

Only the two-argument form lives here. The n-nearest, radius, rule, all-pairs, and NearestTo operator forms, and the DistanceFunction option, are separate follow-ups.

Performance¶

Measured on arm64 Darwin at commit 2dea9cc05.

case	n	time
nearest to a target	1,000	367 us
nearest to a target	10,000	3.5 ms
nearest to a target	100,000	34.3 ms

Implementation notes¶

Algorithm. builtin_nearest (two-argument form) returns the element(s) of a list closest to a target x. nearest_distance forms Abs[element - x] by composing internal_subtract and internal_abs through eval_and_free, so a complex element uses its modulus for free. The shape follows MinimalBy, not a quickselect: one pass finds the minimum distance, a second collects every element whose distance equals it, in input order — so ties are returned together (Nearest[{1, 5, 10}, 3] is {1, 5}) and the tie handling falls out of the ascending collect pass rather than being coded.

Numeric gate. Every distance must be a real number (checked by list_real_number_q), or the whole call declines — this covers a symbolic element, a symbolic target, and a non-real complex in one test, and even rejects a symbolic real such as Pi. The minimum and ties are decided with list_numeric_cmp; an undecidable comparison declines rather than guessing. Nearest[{}, x] is {} (checked before the gate).

Complexity / limits. O(n) distance evaluations and O(n) comparisons, with O(n) peak extra memory; two evaluate passes per element dominate, so this is an interpreter-speed path, not a buffer one — Nearest is deliberately not on pack.c's AWARE list, so a packed argument is materialised and a visible NDArray (not a List) is left unevaluated rather than silently truncated. Only the two-argument form is implemented (no n-nearest, radius, rule or DistanceFunction forms). ATTR_PROTECTED.

Protected.
Distance is Abs[element - x], so a complex element uses its modulus.
All elements tied at the minimum distance are returned, in their original order: Nearest[{1, 5, 10}, 3] gives {1, 5}, not {1}.
Distances are compared by numeric value, so exact and inexact distances of equal value tie: Nearest[{0, 2.0}, 1] gives {0, 2.0}.
An empty list gives {}.
Returns unevaluated unless every distance is a real number. A symbolic element or target leaves the expression unchanged rather than being dropped from the result — unlike MinimalBy, which orders symbolic keys after all numbers and so silently omits them.
A rational with a bigint component declines, because Abs does not evaluate one: Nearest[{1/10^25, 1}, 0] stays unevaluated.
Only the two-argument form is implemented. The n-nearest, radius, rule, and all-pairs forms, the NearestTo operator form, and the DistanceFunction option are not yet available.

Attributes: Protected.

References¶

See also: MinimalBy, Abs

Source: src/list/nearest.c
Specification: docs/spec/builtins/lists-and-iteration.md
Tests: tests/test_list.c
Tests: tests/test_ml_predict.c

Notes & additional examples¶

Notes¶

Nearest[list, x] returns the element (or elements) of list closest to the target x, using Abs[element - x] as the distance. Every element tied at the minimum distance is returned, in the order it appears in the input, so the result is always a list. Nearest[{}, x] is {}.

Every distance must be a real number, or the whole call is left unevaluated — a symbolic element, a symbolic target, a non-real complex, or even a symbolic real such as Pi all decline, rather than silently dropping out of the result. Complex elements are handled through their modulus.