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
