Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #2977

Re: Binary Search

Show all headers | View raw

On 4/7/2011 11:29 PM, Gene wrote:
> This is wrong.  It depends on how long comparisons take.  If comparing two elements requires 1 minute, and the list has 20 elements, then the binary search runs in no more than 5 minutes plus a few microseconds, and the linear search runs in no more than 20 minutes plus a few microseconds.  So you clearly want the binary search.

     There's not much to go on, but I guess you're comparing a binary
search against a linear search in a twenty-element array.  Okay, fine:
The binary search takes <=5 minutes and the linear search takes <=20.
But you can't even *start* to use binary search until you've sorted
the list, which takes about 20*lg(20/2) ~= 66+ comparisons, slightly
over an hour.  By the time you've completed *one* binary search you've
spent 71 minutes; the linear search has spent 20.  After two searches
binary has used 76 minutes and linear has used 40.  After three, binary
is up to 81 and linear is at 60.  Four searches, and linear is still
faster: 86 vs. 80.  It's not until the fifth search that binary finally
overcomes its startup cost and starts to pull ahead.

     "Well, *of course* there will be billyuns and billyuns of searches,"
you say.  Perhaps, but you left that "given" out, didn't you?  You also
left out the "given" that the search keys are not equiprobable; in
fact, one single key accounts for 90% of all searches, another for 9%,
and the remaining eighteen for just 1% -- and the linear list uses
move-to-front.  (It's right there in the third paragraph of the problem
statement, right after the part about the billyuns.)  So in fact the
linear list takes one-and-a-fraction comparisons per search; let's be
generous and say it averages 90 seconds -- *far* faster than a five-
minute binary search.

     In other words: Cost comparisons without context are silly.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Binary Search Gene <gene.ressler@gmail.com> - 2011-04-07 20:29 -0700
  Re: Binary Search Lew <noone@lewscanon.com> - 2011-04-08 00:01 -0400
    Re: Binary Search Patricia Shanahan <pats@acm.org> - 2011-04-07 21:51 -0700
    Re: Binary Search Lars Enderin <lars.enderin@telia.com> - 2011-04-08 08:20 +0200
  Re: Binary Search Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-04-08 00:46 -0400
    Re: Binary Search Gene <gene.ressler@gmail.com> - 2011-04-08 18:26 -0700

csiph-web