Half split method: find a fault by testing the middle first
The half split method finds a fault in a chain by testing the middle first: one test tells you which half holds the fault, and you repeat on that half until one part is left. A chain of 8 parts takes 3 tests and a chain of 64 takes 6, because every test halves what is left to suspect.
In Problem Graph you write the fault down in one line, attach each fix you try and record whether it worked, partly worked or failed, so the next hunt starts from what the last one found.
What the half split method is and what it needs
It is binary search carried out on a real system instead of a sorted list. Wikipedia's article on troubleshooting gives a printing example: check whether the job reached the server, and you know which side of the server the problem is on. It calls this "the application of a binary search across the range of dependencies" and says it is "often referred to as half-splitting".
You need three things before the first test:
- A known good point, usually the input.
- A known bad point, usually the output.
- A test with a clear answer at any point in between: signal or no signal.
You also need a path that runs one way. The same article says the technique "can be particularly efficient in systems with long chains of serialized dependencies". That is the difference from the process of elimination: there each test rules out one cause, here each test rules out half of the chain.
How to do a half split, step by step
- Confirm the two ends. Check that the input really is good and the output really is bad.
- Test the midpoint. Pick the point with about half the suspects on each side.
- Read the result. Good at the midpoint clears everything upstream, so the fault is downstream. Bad puts the fault upstream.
- Move one end. The midpoint becomes your new known good or known bad point.
- Repeat. Stop when the good point and the bad point sit on either side of one part. That part holds the fault.
Why the middle test tells you the most
Each midpoint test removes half of the remaining suspects. With 64 parts the suspects go 64, 32, 16, 8, 4, 2, 1: six tests. Checking in order from one end can take 63, and about 32 on average. Double the chain and the half split needs one more test.
The reason is information. In his 1948 paper A Mathematical Theory of Communication, Claude Shannon defined a measure of how much a choice tells you. It is zero when you are already certain of the outcome, and largest when every outcome is equally likely, which he called "the most uncertain situation".
Check the output of stage 1 of 64, with one fault that could be anywhere, and it reads good 63 times in 64. You nearly knew the answer, so it tells you almost nothing. Check the middle and you cannot predict the answer, which makes it the test worth running.
A worked example: a silent microphone and eight stages
This example is made up. A school hall has a sound system with eight stages in a line: microphone, microphone cable, preamp, equaliser, compressor, mixer channel, power amplifier, and the speaker with its lead. Someone speaks and the speaker stays silent. You can plug headphones into the output of any stage, and each check takes about 2 minutes.
- Test 1, after stage 4 (the equaliser): signal. Stages 1 to 4 are cleared.
- Test 2, after stage 6 (the mixer channel): silence. The fault is in stage 5 or 6. Stages 7 and 8 are never tested.
- Test 3, after stage 5 (the compressor): signal. The fault is in stage 6, the mixer channel.

Three tests, 6 minutes. Checking in order from the microphone would have reached the mixer channel on the sixth check, after 12 minutes. The half split takes three tests whichever stage has failed; checking in order takes from one to seven.
The method tells you where, not why. The channel could be muted or have a loose connector. That is a new, smaller problem, and you test fixes for it one change at a time.
From binary search to git bisect: where the method comes from
Wikipedia's history of binary search gives its first mention as John Mauchly's, in the Moore School Lectures of 1946.
Software later applied it to time instead of space. In 1997 Brian Ness and Viet Ngo of Cray Research described "source change isolation": when an edition of their compilers broke, they needed the one change that broke it. Wikipedia's article on bisection) says they outlined two ways to find it, a linear search and a binary search.
Git now ships the binary version. Its manual says git bisect "uses a binary search algorithm to find which commit in your project's history introduced a bug". You name a bad commit and a good one, and Git picks a commit between them for you to test. The manual's own example prints "Bisecting: 675 revisions left to test after this (roughly 10 steps)".
So you can split a history as well as a chain: if something worked last month and fails today, test the version from the middle of the month.
When the half split method fails
The strongest objection: the method assumes one fault, one direction and a test that tells the truth. Break any of the three and it misleads you.
- More than one fault. The bisection article says the behaviour must change only once across the range. Otherwise the search "will find one of them, but it will not necessarily be the root cause". With faults at stages 2 and 6 in the hall, you find and fix stage 2 and the speaker is still silent.
- Loops. The troubleshooting article says systems with feedback loops are "less amenable" to bisection. When the output feeds the input, no point is upstream of the fault.
- A fault that comes and goes. One wrong "good" sends you into the wrong half, and every test after it is wasted.
Take the last one. Say the fault shows on 1 try in 5, and each try is independent. A clean reading at a point past the fault is then wrong 4 times in 5. Five clean readings in a row still happen by chance 33 times in 100, and it takes 14 in a row to push that under 5 in 100. So make the fault show every time before you split, or repeat each test many times.
How many repeats are enough is still unsettled. Mathematicians study a version of this as Ulam's game: twenty questions in which one answer may be a lie, introduced by Alfréd Rényi in 1961. The game fixes the number of lies in advance. A real fault does not.
Split the likelihood in half, not the parts
This is the distinction people most often get wrong. Shannon's point was about equally likely outcomes, not equal numbers of parts. The two match only when every part is equally likely to fail.
Suppose the hall kept a record of its last 20 faults: 10 in the microphone cable, 3 in the speaker and its lead, 2 in the mixer channel and 1 in each of the other five stages. A test after stage 2 splits the parts two against six, but it splits the record 11 against 9.

Run all 20 faults through each plan. The plain half split takes 3 tests every time: 60 tests. Splitting by likelihood, first after stage 2 and then by halves of what is left, takes 54. Checking in order from the microphone takes 73.
The gain is real but small here: 6 tests in 60. And it is an average: for the mixer channel fault the likelihood split would have taken 4 tests, not 3.
Cost counts too. The troubleshooting article puts a step before any bisecting: check "frequently encountered or easily tested conditions" first. If swapping the microphone cable takes a minute, do that first. None of this is possible without a record of past faults, even a simple tally on a check sheet.
Frequently asked questions
Is the half split method the same as binary search?
Yes. Binary search halves a sorted list to find a value, and the half split method halves a chain to find the point where good turns to bad.
How many tests does the half split method need?
About log2 of the number of parts, for a single fault: 3 tests for 8 parts, 6 for 64, and about 10 for 1,000.
When should you not use the half split method?
When the path loops back on itself, when several faults exist at once, or when the fault comes and goes and you cannot make it show reliably.
Should you always test the exact middle?
No. Test where the two answers are about equally likely, which depends on which parts fail most, and check a very cheap or very likely cause first.
Get started
Problem Graph keeps the record that makes your next split a better one. Write the fault as a problem in one line, such as "No sound from the hall microphone", and put it in the work lane. Attach each fix you try as a solution and record the outcome: worked, partly or failed. A failed fix stays on the map as failed. If the hunt turns up a second fault, write it as its own problem and link the two.
If other people look after the same equipment, mark the fault as a main node and share it into a private network. You give a few people the invite code, and they see the node with its solutions and outcomes. The app page offers a "Load example set" button on an empty graph if you want to see a filled map first.
Try Problem Graph: it is free, and you can look around the public network without an account. Write one problem down in a line and attach the first thing you will try.
Every problem you carry, on one map. Solved together.
Visit problemgraph.vlvd.net↗


Comments
No comments yet.