Implement best_split(X, y), which finds the split at one decision-tree node that minimizes the weighted Gini impurity.

Input

X  # (n, d) two-dimensional array — real-valued features
y  # (n,)  labels, 0 or 1

It may arrive as a list of lists or as a numpy array.

Candidate thresholds

For each feature, sort its values ascending, drop duplicates, and take the midpoint of every adjacent pair as a candidate.

feature values [1, 2, 2, 4] → unique [1, 2, 4] → candidate thresholds [1.5, 3.0]

Splitting and impurity

• Rows with X[:, f] <= t go left; the rest go right.
• Gini impurity: $G(S) = 1 - \sum_c p_c^2$
• Weighted impurity: $\frac{|L|}{n}G(L) + \frac{|R|}{n}G(R)$

Return value and rules

(feature_index, threshold)

• Choose the candidate with the lowest weighted Gini.
• Discard any threshold that leaves one side empty.
• On a tie, prefer the lower feature index; if still tied, the lower threshold.
• If no valid split exists (every feature has a single distinct value), return None.
• Round the threshold to 6 decimal places.

Implement best_split(X, y).

• Return a (feature index, threshold) tuple; the threshold is a float.
• Return None when no valid split exists.
• numpy is fine, and so is plain Python.