Neural Mastery
← Practice
Brute-Force K-Nearest-Neighbor Searchmedium

Brute-Force K-Nearest-Neighbor Search

medium RAG & Retrieval 15–20 min

NumPy allowed · plain Python earns 10 bonus points

RAG step 1/4

A query retrieves context

Embedding similarity ranks the documents before generation.
Open lesson →
01query
02embed
03retrieve
04context
What is RAG?→ embed →top context
retrieval.md44%
rag-systems.md33%
agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement the exact ("flat") k-NN search every ANN index (HNSW, IVF, LSH) is an approximation of -- the ground-truth baseline used to measure the recall of every faster index structure.

Related Skills

Task

Implement brute_force_knn(query, vectors, k): compute the Euclidean distance from query to every row in vectors, and return the indices of the k nearest, sorted nearest-first (ties broken by ascending index).

Function Signature

brute_force_knn(query: list[float], vectors: list[list[float]], k: int) -> list[int]

Examples

Example 1: k=3 Nearest
Input: query = [0, 0] vectors = [[0, 0], [1, 0], [5, 5], [0.5, 0.5], [10, 10]] k = 3
Output: [0, 3, 1]
Example 2: k=2 Nearest
Input: query = [0, 0] vectors = [[1, 1], [2, 2], [3, 3], [10, 10]] k = 2
Output: [0, 1]

Constraints

  • Libraries (NumPy) are allowed and accepted normally.
  • A plain-Python solution earns 10 bonus points.
  • Raise ValueError if k <= 0 or k > len(vectors).
  • Ties in distance must be broken by ascending original index.
Python3Saved ✓
import math

def brute_force_knn(query: list[float], vectors: list[list[float]], k: int) -> list[int]:
"""Return the indices (into vectors) of the k vectors closest to query
by Euclidean distance, ordered nearest-first. Ties broken by index
ascending. Raise ValueError if k <= 0 or k > len(vectors)."""
# Your implementation here
pass

Case 1: k=3 Nearest
Input: query = [0, 0] vectors = [[0, 0], [1, 0], [5, 5], [0.5, 0.5], [10, 10]] k = 3
Expected: [0, 3, 1]
Case 2: k=2 Nearest
Input: query = [0, 0] vectors = [[1, 1], [2, 2], [3, 3], [10, 10]] k = 2
Expected: [0, 1]