Makhno wrote:
> Hello!
> I've been using a binary-search like algorithm for an ordered array of
> time-stamps for ages. It works a bit like this (some code removed for
> clarity):
>
>
> array - array to be searched, where time member is ordered
> count - size of array
> t - time
> i - desired index where (array[i].time<t<array[i+1].time)
>
>
> int i=count/2,n=count;
> for(;;)
> {
> n=n/2;
> if (t>array[i].time)
> i+=n;
> else
> i-=n;
> if (n<=1)
> return i;
> }
>
> It 'usually' works, but I can always find conditions where it doesn't
> and I'm not sure why. It works fine for sorted integers.
>
> Noting the wikipedia page on binary search, it seems most programmers
> mis-program a binary so I've probably made the same mistake!
>
> A linear search like this always gives me the right answer, but takes
> longer:
>
>
> for(int i=0;i<count;++i)
> {
> if (t>array[i].time && t<=array[i].time)
> return i;
> }
>
> I need speed though!
>
> Thanks.
Oh! One more question. What language is this? And what else is in the
data item?
Keep in mind, if you need to add or remove items and find quickly, you
may want to use a tree and many modern languages have pre-existing tree
structures. For instance, TreeSet in Java.
..NET libraries have a convenient Dictionary class, which you may find
useful.
STL libraries can be extended in C++. etc. etc.
Though it is a good exercise if you don't know how, you shouldn't HAVE
TO re-invent the wheel ;)
--
LTP
:)
|
