Re: Fastest Way to Check Word in Dictionary
- Posted by egg Oct 28, 2008
- 1241 views
integer flag one can use sign of the returned value instead of flag
function findPos(sequence s,sequence ss) searching string ss in sorted list s
integer lo,hi,mid,c lo = 1 hi = length(ss)
c = compare(s,ss[1]) if c<0 then found = 0 return 1 elsif not c then found = 1 return 1 end if
c = compare(s,ss[hi]) if c>0 then found = 0 return hi+1 elsif not c then found = 1 return hi end if
while 1 do w = hi - lo if not w then found = 0 return hi elsif w<10 then lo += 1 while 1 do c = compare(s,ss[lo]) if not c then found = 1 return lo elsif c<0 then found = 0 return lo else lo += 1 end if end while else (hi-lo)>=10 mid = floor((lo + hi) / 2) c = compare(s,ss[mid]) if c<0 then x < ss[mid] hi = mid elsif c>0 then x > ss[mid] lo = mid else x = ss[mid] found = 1 return mid end if end if end while end function findPos