best-tree-split — Zoom case

The team needs a reliable implementation for tree split in a production-oriented ML workflow. A subtle implementation error can pass obvious examples while producing incorrect behavior on boundary or distribution-shifted cases.

Evaluate candidate thresholds between sorted feature values and return the threshold with the lowest weighted Gini impurity.

Evaluate every candidate threshold and return the best one. Candidates are the midpoints between consecutive distinct sorted feature values; the score of a threshold is the sample-weighted Gini impurity of the two sides (labels are 0/1), and a later candidate must beat the best by more than ${10}^{-12}10^\{-12\}$, so ties keep the smaller threshold.

Implement solve(x,y).

Returns. Return the threshold as a float, or None if x has fewer than two distinct values.

Examples

Example 1

Input:

solve([1, 2, 4, 7], [0, 0, 1, 1])

Output:

3.0

Example 2

Input:

solve([3.0, 3.0], [0, 1])

Output:

None