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.
I can't follow your logic, probably because of the flaw.
So is it always supposed to find a match? What happens if the match
does not exist?
I suggest calling your variables top and bottom.
And there are 3 cases, not two. One is your pivot point is less than
the target, your pivot point is greater than the target or your pivot
point equals the target. You exit if top<bottom.
And i+=n and i-=n make no sense at all. In a true binary search just
keep adjusting your top and bottom, and since you didn't match on your
pivot increment it or decrement it depending on the case.
To be honest, I'm surprised that code works ever.
If what you are trying to do is drastically different than finding a
value in a sorted list, then I apologize. I guess I don't understand.
Further, I suggest you make test cases and test any function you write
with a couple thousand test cases of random data with different array
sizes.
Also, are these just integers? What are their ranges? There may be
something far faster than a search (like a hash or array lookup) if
speed is really so im****tant.
1. What is the case when something isn't found
2. What is the data type
3. How many items are there
4. What are the data ranges on the items
5. Are there ever duplicates
6. Anything extra? (They are expected to be sequential, they need to be
able to remove quickly etc)
With this information we may be able to suggest a better approach (even
if I did do lousy in my last topcoder match . . bleh)
--
LTP
:)
|
