# Computer Chess Club Archives

## Messages

### Subject: Re: Book design

Author: Andreas Herrmann

Date: 11:44:22 11/28/02

Go up one level in this thread

```On November 28, 2002 at 14:40:30, Andreas Herrmann wrote:

>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
>>
>>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
>
>the book of Holmes works in this way. It costs only a few milliseconds to find
>the right entry in the book file. So the time should not be the problem, and
>this is the normal way to search in sorted data.

I meant: "should be NOT a problem"

>
>My old book has about 109.000 different position entrys and there were a maximum
>of 17 comparisons to find the right position. My new book has over 1,7 million
>different positions and the maximum of comparisons is here 21.
>
>max.      until n
>accesses   entrys
>-----------------
> 2              3
> 3              7
> 4             15
>...
>15          32767
>16          65535
>17         131071
>18         262143
>19         524287
>20        1048575
>21        2097151
>...
>
>have a nice day
>Andreas

```