KNN Neighbour Lookup

k-nearest-neighbours does no training at all. To classify a new point it simply finds the k stored points closest to it and lets them vote. This problem is the lookup half: finding those neighbours.

Task: write k_nearest(points, query, k) returning the positions of the k closest points to query, ordered nearest first.

Distance is straight-line (Euclidean) distance:

• points is a list of points; query is a single point with the same number of coordinates. Any number of dimensions.
• Return indices into points, not the points themselves. That's what lets you look up each neighbour's label afterwards.
• If two points are the same distance away, the one with the lower index comes first.
• k is never larger than the number of points.

Notice that you never need the square root to decide an ordering — squared distance ranks points identically, since squaring is increasing for non-negative numbers. Skipping the sqrt is the standard optimisation here, and it changes nothing about the answer.