This is a
solution to
problem 30 on the
hard interview questions node. If you have not read the
question, the
following will make no
sense to you:
Let the processors be numbered 1...n. Begin by asking processor 1 if processor 2 is good. If the answer is "no", remove these two processors from the list and start over. Note that you removed one good processor and one bad processor from the list, so more than half of the remaining processors are still good.
If processor 1 says processor 2 is good, continue by asking processor 2 about processor 3, 3 about 4, etc., until you get a "no" answer. Suppose it is processor j that says processor j+1 is bad. Remove both processors j and j+1 from the list (as before, more than half of the remaining processors are still good, since one of the two you removed was good and one was bad), and continue by asking processor j-1 about processor j (the processor that was after j+1 before you removed it and the original processor j).
You are creating a "chain" of processors who each think the next processor in the chain is good. So these processors are either all good or all bad. Once this chain comprises more than half of the processors in the remaining list, you know that all these processors are good. Or, if you've removed so many processors that only one or two remain, you know that that one or those two are good.
To show that this involves at most n-2 steps, note that every processor is asked about at most once, and the first processor is never asked about. Also, the last processor is never asked about either, since you stop once the chain is longer than half the list.