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