Shannon-Fano Split

Problem

Given probabilities in descending order, choose the split index k in 1..n-1 that minimizes the absolute difference between the sum of the first k probabilities and the sum of the rest. Return k, breaking ties toward the smaller index.

Hint

Scan every split point; the probabilities are already sorted so the halves stay contiguous.

Test cases

case 1

in: [[0.5,0.25,0.25]]

expected: 1

case 2

in: [[0.4,0.3,0.2,0.1]]

expected: 1

case 3

in: [[0.25,0.25,0.25,0.25]]

expected: 2

case 4

in: [[0.6,0.2,0.2]]

expected: 1

case 5

in: [[0.7,0.1,0.1,0.1]]

expected: 1

Starter codePython

def shannon_fano_split(probs):
    # Your code here
    pass

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