Michael, I can't speak for other participants in this thread, but I for one just felt a rare desire to post. Did I have to get your approval?
Yes, this is an almost obvious solution. However, previous entries were discussing travesing the list back and forth to emulate binary search ... And while I do admire Knuth since I read his first 3 volumes in the late 70s, I don't recall the last time I had actually looked them up for my day- to-day duties. Especially, to traverse a B-tree ... Thanks anyway, -Victor- On Wed, 18 Jan 2012 13:45:24 -0600, Michael Stack <[email protected]> wrote: >While binary search trees have been mentioned (by John Gilmore, IIRC), I keep wondering why so many other solutions are being suggested. For any repetitive search of a linked list, converting to a BST seems an almost obvious solution. See Knuth's Algorithm 6.2.2T (Tree Search and Insertion), for example. Or am I missing something? > >Michael Stack > >At 01:47 PM 1/18/2012 -0500, Victor Gil wrote: >>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-
