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 >>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 > >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
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.