> So is it always supposed to find a match? What happens if the match
> does not exist?
It isn't finding a match. The item may not be in the list. I'm looking
for items that bracket it.
> 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.
This, and trivial list cases, were 'removed for clarity'.
> 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.
yes I did, I just didn't use a top and bottom, but rather an index 'i'
and and offset 'n' which keeps halving.
> To be honest, I'm surprised that code works ever.
It's been working for literally years. I'm now chasing bugs.
> 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.
The list is a list of floats, and the value is a float that may, but is
probably not, in the list. There will be values that bracket it though.
Imagine recording (and time-stamped) 'frames', and attempting to find
the two frames around the current playback time (perhaps for
interpolation).
> 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.
Will do. But i have nothing to start with.
> Also, are these just integers?
I thought it was clear. Timestamps are unlikely to be integers.
I have noticed that my code seems to work fine for integers however, but
this is not useful to me.
> 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.
Nope.
Thanks for the reply!
|
