$k$-means partitions numerical data into $k$ clusters by representing each cluster with a centroid.

Given centroids $\mu_1,\ldots,\mu_k$, each example is assigned to its nearest centroid. The objective is

$$\sum_{i=1}^n |x_i-\mu_{c_i}|^2,$$

where $c_i$ is the assigned cluster.

Lloyd's algorithm alternates two steps:

1. assignment: assign every point to its nearest centroid;
2. update: replace each centroid by the mean of the points assigned to it.

For one-dimensional points $1,2,9,10$ with $k=2$, starting near 1 and 9 quickly gives clusters ${1,2}$ and ${9,10}$ with centroids $1.5$ and $9.5$.

Each iteration cannot increase the objective, but the algorithm can converge to different local optima from different initializations. Multiple restarts or careful initialization such as k-means++ are therefore common.

Because the objective uses squared Euclidean distance, feature scaling strongly affects the result. The method also favors roughly compact, spherical clusters and can represent elongated or unequal-density structures poorly.