> If you split into multiple parts, each part of the key is useful: it lets you reduce your search space by however many bits of the key you have.
That doesn't have to be true. Rather than splitting an AES key K into substrings, a better approach is to choose n parts such that:
K_1 ^ K_2 ^ ... ^ K_n = K
None of the component K_i will reveal any information about K without knowledge of its peer components.That's fine if you are willing to require all n parts to be available to reconstruct the key.
In many applications, though, you want to allow a subset of the parts to reconstruct the key. You might want, say, 8 people to have key shares, but want any 3 of them to be able to reconstruct the key. Shamir's makes this kind of setup easy.
I wouldn't call that "splitting". This is how you do shamir's scheme over GF(2^n) when the number shares equals the threshold.
Slightly more concretely: I can split a secret value s into two parts by randomly choosing a line that has X intercept s, then giving the value of the line at 1 and at 2. Neither of these alone gets me any closer to finding s, but if I know them both, then I can trivially get s.
Also, splitting the parts up directly means you can't do "any t of n is good enough" where t != n and t != 1.