Breakpoint Detection Binary Segmentation

Problem

Find the best single changepoint by binary segmentation: for each split index i in 1..n-1 compute the total within-segment sum of squared deviations plus penalty, and return the i that minimizes this cost.

Return -1 if no split beats keeping the series whole by more than 1e-12, for example when the penalty is too large.

Hint

Segment cost is the within-segment sum of squared deviations from the segment mean.

Test cases

case 1

in: [[0,1,0,1,10,11,10,11],1]

expected: 4

case 2

in: [[-1,0,1,2,3],10]

expected: -1

case 3

in: [[1,2,3,10,11,12],0.5]

expected: 3

case 4

in: [[5,5,5],0]

expected: -1

Starter codePython

def binary_segmentation(series, penalty):
    # Your code here
    pass

4 test cases · run your code against them in the editor