### binary search with reference to append

- Posted by gimlet Jun 13, 2014
- 2004 views

This is an example of why you should require the caller validates the parameters of a called function.

This is a summarised version of the binary_search function in /std/search.e

The notes make interesting reading:

The function messes with its parameters. The result is not pretty.

function bsearch(obj x, seq A, int sp=1, int ep=0) int N, lo, hi, mid, c --------------------- N = length(A) 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 --------------------- mid = sp -- this is unwise c = 0 -- the match (set to 0 - found) -- at this point consider -- if lo > hi we have mid = sp, c = 0, a return of -sp (sp may be -ve) -- if N = 0 then -- if lo <= hi we have a crash. -- if lo > hi we have mid = sp, c = 0, a return of -sp (sp may be -ve) -- if N != 0 then -- if lo <= hi then the loop executes. -- if lo > N we have a crash. -- if lo <= N then -- if hi > N we have a potential crash. -- else we are OK. -- -- Perhaps this is complicated enough for you to believe there is a problem! -- -- Perhaps you may say this is all so remote because 'almost always' it suceeds -- (code for only a countable infinty of failures). while lo <= hi do mid = floor((lo + hi) / 2) c = eu:compare(needle, haystack[mid]) if c < 0 then hi = mid - 1 elsif c > 0 then lo = mid + 1 else return mid end if end while -- return the position it would have, if inserted now if c > 0 then mid += 1 end if return -mid -- if A was null then any return was nonsense -- if A was not empty was the range sp..ep valid? end function

Tell me, in how many ways is that function wrong?