OpenEuphoria

binary search with reference to append

• Posted by gimlet Jun 13, 2014
• 1996 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?