Re: Fastest Way to Check Word in Dictionary

new topic     » goto parent     » topic index » view thread      » older message » newer message

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

it returns index of found string or insertion position if flag=1 then string was found

if flag=0 then string was not found

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

new topic     » goto parent     » topic index » view thread      » older message » newer message

Search



Quick Links

User menu

Not signed in.

Misc Menu