wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Two binary search surprises
        
(Message started by: Amir Michail on Sep 25^th, 2004, 10:46pm)

Title: Two binary search surprises
Post by Amir Michail on Sep 25^th, 2004, 10:46pm

Two things that you might find surprising about binary search:

(1) Binary search is not optimal for expensive comparisons

http://geomblog.blogspot.com/2004/08/sorting-vs-searching.html

(2) Binary search on an unordered array can give meaningful results:

http://cgi.cse.unsw.edu.au/~ideas/index.php?module=articles&func=display&ptid=1&aid=387

Amir

Title: Re: Two binary search surprises
Post by Amir Michail on Dec 28^th, 2004, 1:31pm

The paper for (1) is now available:

http://ideas.web.cse.unsw.edu.au/index.php?module=articles&func=display&ptid=1&aid=423

Amir

P.S. Feel free to bet on papers in the Speculative Search Game. See for example the game link mentioned for this paper:

http://ideas.web.cse.unsw.edu.au/index.php?module=articles&func=display&ptid=1&aid=422

I plan to enter more (query, url) pairs for CleverCS papers, but any help would be appreciated in this regard.