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