Decision Tree: Best Split

This is how a decision tree actually makes a decision: try every question it could ask, score each one, and keep the winner. There's no cleverness to it — it's a brute-force search, and the whole algorithm is in how you enumerate the candidates.

Task: write best_split(features, labels) returning [feature_index, threshold] — the single best question of the form "is feature f at most t?".

How to enumerate the candidate thresholds for one feature:

1. Collect that feature's values, de-duplicated and sorted.
2. For each neighbouring pair, the candidate threshold is their midpoint: (a + b) / 2.

That's it — midpoints between observed values, so a threshold always sits in a gap rather than on top of a data point.

To score a candidate, split the rows into left (feature value ≤ threshold) and right (greater), and compute the size-weighted Gini impurity of the two groups. Lower is better.

Tie-breaking, in this order: lowest impurity wins; on a tie, the lower feature index; on a further tie, the smaller threshold.

• features is a list of rows, all the same length. labels lines up with it.
• Every feature has at least two distinct values, so there's always at least one candidate.
• Round the returned threshold to 4 decimal places.

A feature with k distinct values offers k - 1 questions, so the search is wider than it first looks — and this one function, called recursively on each side, is a whole decision tree.