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
