While binary search trees have been mentioned (by John Gilmore, IIRC), I keep wondering why so many other solutions are being suggested. For any repetitive search of a linked list, converting to a BST seems an almost obvious solution. See Knuth's Algorithm 6.2.2T (Tree Search and Insertion), for example. Or am I missing something?
Michael Stack At 01:47 PM 1/18/2012 -0500, Victor Gil wrote: >How about this - run through the linked list and collect ALL pointers into >an array[1:M]. > >Then do binary search on the array? > >HTH, >-Victor- > >On Wed, 18 Jan 2012 10:42:11 +0100, Rob van der Heij <[email protected]> >wrote: > >>On Tue, Jan 17, 2012 at 10:23 PM, Robert A. Rosenberg <[email protected]> >wrote: >> >>> 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. >> >>Running backward requires a double-linked list. Without that, you have >>to start at the front again when the key comparison shows you're past >>the point. Keeping bread crumbs could save you one trip, but would >>make the pointer chase more costly unless hardware does it. >> >>Rob
