Computer Chess Club Archives




Subject: Re: Book design

Author: David Rasmussen

Date: 10:56:47 11/28/02

Go up one level in this thread

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.


This page took 0 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.