Re: binary search with reference to append
- Posted by jimcbrown (admin) Jun 13, 2014
- 1824 views
This is an example of why you should require the caller validates the parameters of a called function.
While I agree with "you should require the caller validates the parameters of a called function", I don't think this is a good example.
The function messes with its parameters.
No, it does not modify it's parameters.
lo = max(sp, 1) -- lo could be > N hi = min(N, ep) -- hi could be < lo hi = (lo > hi && N) ? N : hi -- hi could be > N
Agreed, a sanity bounds check here would not hurt - but if sp or ep is out of bounds, it's an error. (Ideally, it'd be an exception or a flag, not an uncatchable run-time error.)
mid = sp -- this is unwise
That is harmless, as in the case where lo <= hi, mid is immediately reset without the old value being used. So this is for the case where lo > hi, in which case the function returns immediately, stating that the record would be inserted into the first position. (Actually, maybe this only makes sense when dealing with the empty sequence?)
c = 0 -- the match (set to 0 - found)
Again, harmless. In the case where lo <= hi, c is immediately reset without the old value being used as well. Where lo > hi, c=0 is still harmless, it just means we don't adjust the offset returned by 1 (as we would do in the case where lo<=hi but the item was not found and the last object in the haystack search range < needle).
-- at this point consider -- if lo > hi we have mid = sp, c = 0, a return of -sp (sp may be -ve)
What the heck is ve? Anyways, this case is designed for the empty sequence. I concede that if sp and ep are both longer than the length of the sequence, the return value here may be weird, causing logic errors or a run-time crash later on.
-- if N = 0 then -- if lo <= hi we have a crash.
If both sp and ep are out of bounds. Conceded. Maybe this is the right thing to do, though, since we normally crash on out of bounds errors and it's better to fail early.
-- if N != 0 then -- if lo > N we have a crash. -- if lo <= N then -- if hi > N we have a potential crash.
So if either sp or ep are out of bounds, we could have a crash. I don't like the 'potential crash' here, I think if it's out of bounds, we should detect it early and report back on it somehow.
So, that's definitely a bug. Conceded.
-- if N = 0 then -- if lo > hi we have mid = sp, c = 0, a return of -sp (sp may be -ve)
Didn't you already say this?
Perhaps you may say this is all so remote because 'almost always' it suceeds
No, you've definitely found something here. 'almost always' is not good enough in this case.
if A was null then any return was nonsense
"A was null" means "A = {}" ? Assuming that this is what you mean,
Yeah, I need to think about this one some more.
if A was not empty was the range sp..ep valid?
Yes, that definitely needs to be checked. But what to do if there's an out-of-bounds error?
Tell me, in how many ways is that function wrong?
Just one - lack of proper bounds checking.
