wu :: forums
« wu :: forums - Two binary search surprises »
Welcome, Guest. Please Login or Register.
Apr 30th, 2024, 1:23pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   general problem-solving / chatting / whatever (Moderators: Eigenray, Icarus, Grimbal, SMQ, towr, william wu, ThudnBlunder)
   Two binary search surprises		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Two binary search surprises  (Read 579 times)
Amir Michail
Guest

Email
Two binary search surprises  
« on: Sep 25th, 2004, 10:46pm »		 Quote Quote Modify Modify Remove Remove
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=dis play&ptid=1&aid=387
 
Amir
IP Logged
Amir Michail
Guest

Email
Re: Two binary search surprises  
« Reply #1 on: Dec 28th, 2004, 1:31pm »		 Quote Quote Modify Modify Remove Remove
The paper for (1) is now available:
 
http://ideas.web.cse.unsw.edu.au/index.php?module=articles&func=disp lay&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=disp lay&ptid=1&aid=422
 
I plan to enter more (query, url) pairs for CleverCS papers, but any help would be appreciated in this regard.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board