Rob, My point was the truism that if pointer chasing is cheap and comparisons are not cheap then pointer chasing is advantageous.
Let n be the number of elements in a list and m = 1 + n /2 be the serial number of a middling element. Then chasing pointers (without making comparisons) to find the m-th list element and making the search-argument-to-key comparison there permits one to then proceed in an obvious way as in traditional binary search. The list is treated as a species of array with pointer chasing replacing addressing arithmetic. Some APL implementations do things like this in managing their arrays, which are really lists. The trick here (as elsewhere) is to work with pointers to pointers, so that one always has access to both the location and value of a chaining pointer. John Gilmore, Ashland, MA 01721 - USA
