Author: Andreas Herrmann
Date: 11:40:30 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 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. 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.