Best Binary Split

Find the best threshold for splitting one numeric feature x against class labels y. Candidate thresholds are the distinct observed values of x except the largest; the split is x <= t versus x > t, and its score is the weighted Gini impurity of the two sides. Pick the lowest score, preferring the smaller threshold on ties.

Implement solve(x,y).

Returns. Return a tuple (weighted_gini, threshold), or None if x has fewer than two distinct values (no valid split).

Examples

Example 1

Input:

solve([1.0, 2.0, 3.0, 4.0], [0, 0, 1, 1])

Output:

(0.0, 2.0)

Example 2

Input:

solve([1.0, 2.0, 3.0, 4.0, 5.0], [0, 1, 0, 1, 1])

Output:

(0.266667, 3.0)

Example 3

Input:

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

Output:

None