At 10:13 PM +0100 20-01-00, Thomas Ward wrote:
>I am getting some very strange behavior from SysBinarySearch. Specifically,
>about half the time it seems to return one greater than the correct answer.
>That is, the element I am searching for is in array[20] and yet
>SysBinarySearch returns 21. The rest of the time it gives the correct
>answer. Even more confusing is that it doesn't seem to happen on all
>versions of the OS.
SysBinarySearch changed in the 3.1 release. (or maybe it was the 3.0
release... I forget, I'm getting old.)
The older version had several bugs, one of them is the one you describe.
If you want a reliable binary search, just put the code from the new
SysBinarySearch into your own app, or (even better), write your own binary
search routine based on the algorithm below. (You can improve performance
a lot by de-generalizing the routine, e.g. getting rid of the call back for
the test.)
--Bob
Boolean YourVeryOwnBinarySearch (void const * baseP, const Int16
numOfElements, const Int16 width, SearchFuncPtr searchF, void const *
searchData, const Int32 other, Int32 * position, const Boolean /*
findFirstNoLongerUsed */)
// note: findFirst (last param) is now ignored, algorithm always returns
// leftmost match
// note(2): please don't write to me and tell me this algorithm can be
// 'improved' by paying attention to this. Do the analysis!
{
Int16 lPos = 0;
Int16 rPos = numOfElements - 1;
Int16 mPos;
// keep going until the pointers cross, that way
// you get the index of smallest (leftmost) elt >= item
// NOTE: (may return Length(array))
while (lPos <= rPos)
{
mPos = (lPos + rPos) / 2;
// mid value < search value
if (searchF(searchData, (UInt8 *)baseP+mPos*width, other) > 0)
lPos = mPos + 1;
else
rPos = mPos - 1;
}
*position = lPos;
// if we've gone off the right end, don't do the final compare
if (lPos >= numOfElements)
return false;
// otherwise, may not have checked current element for equality
// so do it now
return (searchF(searchData, (UInt8 *)baseP+lPos*width, other) == 0);
}
_______________________________________________________________________
Bob Ebert, Sr. Software Engineer, Palm Computing Inc., 3Com Corporation
V: 408 326-9299 5400 Bayfront Plaza, MS: 10212, Santa Clara, CA, 95052
F: 408 326-9891, [EMAIL PROTECTED] (preferred: [EMAIL PROTECTED])
