Binary search of an ORDERED linked list is in fact possible if one knows/keeps track of how many elements the list contains.
It may even be be a useful thing to do when pointer-chasing operations are very much faster than key-comparison operations, as they are in, say, C. My gut feeling about doing it in assembly language is is that it would probably not be faster than Knuth's classical scheme of linear search for a glb followed by an additional equality-checking comparison of any bound obtained. Binary search in an explicit binary-search tree is of course easy. John Gilmore, Ashland, MA 01721 - USA
