At 14:16 +0100 on 01/17/2012, Rob van der Heij wrote about Re: How do you do a binary search on a linked list?:
Ok, I see... Imagine we have an efficient operation that can run M pointers. You'd run to N/2, do your compare and use the result to optionally reset to the start again, and then run for N/4.
IOW: Run the chain to N/2 and see if we are the High or Low. Then run forward or backward N/4 pointers (ending up at N/4 or N*3/4 [ie: 1/4 or 3/4 into the chain]). Each time you half the distance between the current location and half way forward/backward to the prior location until you get a hit or have bracketed the location to insert a new record.
