Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Book design

Author: Sune Fischer

Date: 11:10:33 11/28/02

Go up one level in this thread


On November 28, 2002 at 13:56:47, David Rasmussen wrote:

>On November 28, 2002 at 05:13:56, Sune Fischer wrote:
>
>>
>>Can you reveal a few details here :)
>>Binary search, how do I do that?
>>
>
>Suppose you have an ordered list of integers:
>
>1  3  4  7  11  19  20 25
>
>If you're looking for an element in this list, you can search it linearly, from
>beginning to end. For a list of n elements, that takes n comparisons.
>
>Or you can start in the middle of the list, and check whether that element is
>smaller og larger than the element your looking for. If it is smaller, you do
>this whole thing again recursively on the right, higher part of the list. If
>not, you do it on the left, lower part. This takes log2(n) comparisons. Even if
>you have a million entries, is still only takes 20 comparisons. Of course, if
>you have an old slow disk, this can still hurt, as they are 20 random access
>reads. But on the hardware I have access to, it is not a problem.
>
>It is not hard to improve this scheme so that much less disk access, but I
>haven't had any reason to improve it yet.
>
>/David

Yes, bisection is fast, so you then store the keys in ascending order?
I guess it doesn't work if you just put things in there by random.

I am beginning to like this format I think :)

-S.



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.