Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Binary Search Date: Fri, 08 Apr 2011 00:46:34 -0400 Organization: A noiseless patient Spider Lines: 31 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Fri, 8 Apr 2011 04:47:08 +0000 (UTC) Injection-Info: mx01.eternal-september.org; posting-host="KiwfXDyOjqGhZBXcfNnZBg"; logging-data="14854"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX181UTvooLLH1aneUnC9cgJl" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9 In-Reply-To: Cancel-Lock: sha1:a7Na9ZljVRaLL4O2Hoh2wzFaYDI= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:2977 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