At 10:42 +0100 on 01/18/2012, Rob van der Heij wrote about Re: How do
you do a binary search on a linked list?:
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
So long as you remember where you started the last search, you can go
"backward" even with a single linked list by going forward from the
last start point. Here is an example:
Start to 50%. - Result Low
50% to 75% - Result Low
75% to 87.5% - Result High
75% to 81.25% etc
BTW: You can go double linked with only one link field so you can go
backwards and forwards any time you want.
The head points at the first entry and the foot points at the last
entry. Each pointer in an entry contains the address of the next and
prior entry XOR'ed together. Here is an example:
Head->A<->B<->C<->D<->E<->Foot
If I went forward from Head to D and I want to go backward towards
Head, I know I came from forward from C so I just XOR D's address
with the content of C's link field to yield B.
If I want to add C1 between C and D, I create it and place C's
address XOR'ed with D's address into its link field. I then update
C's and D's link field by XOR'ing their contents with the address of
C1.
Removing an entry is done by the reverse. To remove B so A points at
C, you just XOR B's address into A's and C's link fields.
One Note: With this system as opposed to two separate link fields
(one forward and one backward) you MUST run the chain from head or
foot to find an entry - you can not just look at an entry and find
who points at it since the single link field contains a value which
is an encrypted value not a direct address - Only the content of the
Head and Foot pointers are directly usable addresses.
