Implement Euclidean distance and k-nearest neighbors

You are tasked with implementing two core functions for working with points in an n-dimensional Euclidean space. Each point is represented as a list (or array) of numeric coordinates.

Assumptions

• Each point is represented as list[float].
• For any given operation, all points involved have the same dimensionality (same length of the list).
• For the k-nearest-neighbors function, assume 1 <= k <= len(dataset).
• If two points are at exactly the same distance from the query point, break ties by selecting the point with the smaller index in the dataset first.

Part 1: Compute Euclidean distance between two n-dimensional points

Write a function that computes the Euclidean distance between two points in n-dimensional space.

Function Requirements

• Input: Two points, p: list[float] and q: list[float].
• Output: The Euclidean distance as a float.
• Behavior:
  • Handles points of arbitrary dimensions, as long as both input points have the same dimension.
  • The Euclidean distance between points p and q in n dimensions is given by the formula: distance(p,q) = sqrt(sum_{i=1 to n} (p_i - q_i)^2)

Examples

• Distance between [1, 2] and [4, 6] in 2D space.
• Distance between [1, 2, 3] and [4, 5, 6] in 3D space.

Part 2: Find k-nearest neighbors using Euclidean distance

Using the Euclidean distance function from Part 1 as the distance metric, write a function to find the k-nearest neighbors of a query point within a dataset.

Function Requirements

• Input:
  • query_vector: list[float] — the query point.
  • k: int — the number of nearest neighbors to return.
  • dataset: list[list[float]] — a list of data points, where each data point is a list of floats of the same dimension as query_vector.
• Output: A list[int] of the indices of the k nearest neighbors in dataset.
• Behavior:
  • Computes the Euclidean distance from the query_vector to each point in dataset.
  • The returned list of indices must be sorted in order of increasing distance to the query.
  • If two points have the same distance, the point with the smaller original index in the dataset should appear first.

Example Dataset

dataset = [
    [10, 11, 12],  # index 0
    [1,  2,  3],   # index 1
    [4,  5,  6],   # index 2
    [7,  8,  9],   # index 3
    [13, 14, 15]   # index 4
]

Given some query_vector and a value of k, your function should return the indices of the k closest points from this dataset, ordered from closest to farthest.