Re: binary search with reference to append
- Posted by jimcbrown (admin) Jun 14, 2014
- 1685 views
You have misunderstood.
No, I haven't.
The issues are:
The logic of the input checks is wrong.
Agreed.
The handling of empty sequences is wrong.
(if you haven't searched you haven't got a position,
This is complicated by the requirement to return a "potential" position for the new item. I'll call this the jaygade point, in honor of the recent work jaygade has done in this area.
setting mid to sp is arbitrary,
Agreed. Thinking it over, for the empty sequence case, the result should laways be -1, as any item inserted into an empty sequence will be inserted into the first position. The way the default parameters are set up, this is what actually happens, but it could be made more explicit I suppose.
Now, if the user specifies an empty sequence and an invalid range (e.g. 5..9) then it gets weirder. I'm still not sure what to do here.
something is a bit funny at the caller's end)
Non sequitor?
The principles of design involved are:
caller contracts to provide valid input.
called contracts to provide valid output for valid input.
GIGO?
If the called function can return bad output for bad inputs, then the called function should be responsible for checking those conditions.
No. that is in contradiction of
the caller should check its inputs.
The called function is at liberty to
plough ahead or whatever.
Sounds like GIGO.
Therefore
1 Calling bsearch with an empty sequence should return NOT FOUND.
No search was made.
See the jaygade point above.
2 Calling bsearch with sp > ep is the same as calling with an
empty sequence.
Returning -sp is simply wrong.
You might have a point here. I have to think about this some more.
Perhaps in this case, a NOTFOUND/INVALID/NOTARESULT/NOTAPOSITION return value would make sense. Like
public constant NOTAPOSITION = ""
I see where the idea to return -sp came from though. If we return -1 for an empty sequence searching over the entire range, then conceptually {}[5..4] is still an empty sequence, and returning -sp (or -5 in this example) just signifies that if you filled the sequence up to the starting point of the range, then you'd want to insert this item at position 5.
3 Calling bsearch with out of bounds sp, ep should result in
'whatever'. It could crash return a value.
It's the caller's problem.
Again you have a good point here. If only for one minor hiccup, I'd completely agree with you here.
I hate how euphoria's error handling works. No way to catch exceptions. It's embarrassing. Hence, I like to promote the idea that the stdlib return a INVALID_RESULT in place of crashing.
In lieu of being able to throw a catchable ArrayOutOfBoundsException here, I think I've settled on favoring returning NOTFOUND/NOTAPOSITION/INVALIDPARAMETERS or something in this case.
Most of what I wrote was itemising how things go wrong if bsearch messes with its parameters. And fiddling lo and hi in arbitrary ways is most definitely messing even though sp and ep are not changed.
lo/hi are not parameters. sp and ep are parameters. Thus your basic premises are wrong.
Are there any cases where wrong parameters will return erroneous or indeterminate information instead of crashing?
Yes: there are.
I also concur.
Did you mean the caller should check bounds (which is true, IMO) or that the called function should check bounds (which seems to be your example)?
The caller should check.
Here the callee is checking.
The point is that the callee checking creates problems.
I find it odd that you say this but then have the callee check bounds in your later examples in the same post.
2 Binary search does not require a sorted array.
If you consider something like:
A[lo] < x < A[hi] -- lo < hi m = mid(lo,hi) -- We have one of A[m] = x A[lo] < x < A[m] A[m] < x < A[hi]
and so on
That's only true if it's sorted in a particular direction. Here's a counterexample:
-- lo = 1 -- hi = 3 -- x = 2 -- A = {3, 1.5, 1} A[lo] < x < A[hi] -- lo < hi -- but this is not true! -- A[lo] = A[1] = 3 -- A[hi] = A[3] = 1 -- 3 < 2 -- false! -- 2 < 1 -- false! m = mid(lo,hi) -- m now equals 2 -- We have one of A[m] = x -- false, A[m] = A[2] = 1.5 != 2 A[lo] < x < A[m] -- also false A[m] < x < A[hi] -- also false
You say the caller should validate.
Yet you still insist on bsearch rejecting invalid inputs.
Surely all bsearch needs to do is return correct results for
valid input.
But it already does! It's only the invalid input cases that are being argued!
Even simpler would be to drop parameters sp, ep altogether
and pass the slice A[sp..ep] and x.
I wonder if you have a legitmate point, or you are simply just trying to get functionality removed from the stdlib.
