Best split threshold for a continuous feature

The problem, from first principles

A categorical feature splits a node by value; a continuous one has infinitely many possible cut points. Fortunately only cut points between observed values can change which samples go left, so a finite set of candidates is enough.

From theory to code

Implement best_threshold(x, y). Sort the distinct values of x, take the midpoint of every pair of consecutive values as a candidate threshold, send samples with x <= t left and the rest right, and return the candidate with the highest information gain (base-2 entropy) together with that gain.

Constraints

• x is a one-dimensional float array and y an integer label array of the same length; neither is guaranteed sorted.
• Return a tuple (threshold, gain) of two Python floats.
• On ties, return the smallest threshold.
• If x has fewer than two distinct values there is nothing to split: return (None, 0.0).

Hints

Open one at a time. Each gives away a little more than the last.