Re: binary search with reference to append
- Posted by gimlet Jun 14, 2014
- 1856 views
You have misunderstood.
The issues are:
The logic of the input checks is wrong.
The handling of empty sequences is wrong.
(if you haven't searched you haven't got a position,
setting mid to sp is arbitrary,
something is a bit funny at the caller's end)
The principles of design involved are:
caller contracts to provide valid input.
called contracts to provide valid output for valid input.
Therefore
1 Calling bsearch with an empty sequence should return NOT FOUND.
No search was made.
2 Calling bsearch with sp > ep is the same as calling with an
empty sequence.
Returning -sp is simply wrong.
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.
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.
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.
Are there any cases where wrong parameters will return erroneous or indeterminate information instead of crashing?
Yes: there are.
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.
If the function will cause a crash with bad inputs, then I would suggest that it's the caller's responsibility to ensure that it calls the function with the correct parameters.
Quite so.
I mean, we can fail if sequence A isn't sorted in ascending order. Whose responsibility is it to check that condition? The caller or the called function?
1 Well it would have to be the caller as otherwise there would be
no point in using binary search at all.
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
Binary search is the mean value theorem. Ref:
van Gasteren, Netty; Feijen, Wim (1995).
"The Binary Search Revisited"
nItems = length(haystack) if endp = 0 then hi = nItems else hi = endp end if if hi <= nItems and startp <= hi then lo = startp else abort(1) end if while lo <= hi do midp = floor((lo + hi) / 2) switch eu:compare(needle, haystack[midp]) do case -1 then hi = midp - 1 case 0 then return midp case +1 then lo = midp + 1 end case end while -- Not found return 0
If startp > endp, but both are less than nItems, I think that either failure OR returning 0 is a valid response so long as it's documented. Failure could be better during debugging in order to catch invalid inputs when reasonable.
In this case it is reasonable to check the boundaries of the search, but it is not necessarily reasonable to check to see if the haystack is sorted.
This illustrates that the caller should validate the data before sending it to the bsearch function, and that the bsearch function should reject invalid inputs.
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.
function bsearch(seq A, obj x, int sp, int ep) int lo = sp int hi = ep int m, c if length(A) = 0 or sp > ep then return 0 end if while lo <= hi do m = floor((lo+hi)/2) c = compare(x, A[m]) switch c do case -1 then hi = m-1 case 0 then return m case +1 then lo = m+1 end switch end while -- Not found if c = 1 then m = m+1 end if if m > sp and m <= ep then return -m else return 0 -- no position found end if
Even simpler would be to drop parameters sp, ep altogether
and pass the slice A[sp..ep] and x.
function bsearch(seq A, obj x) int lo = 1 int hi = length(A) int m, c if hi < lo then return 0 end if while lo <= hi do m = floor((lo+hi)/2) c = compare(x, A[m]) switch c do case -1 then hi = m-1 case 0 then return m case +1 then lo = m+1 end switch end while -- Not found if c > 0 then m = m+1 end if if m > 1 and m <= length(A) then return -m else return 0 -- no position found end if
