16 lines
466 B
Text
16 lines
466 B
Text
function binary_search(sequence s, object val, integer low, integer high)
|
|
integer mid, cmp
|
|
if high < low then
|
|
return 0 -- not found
|
|
else
|
|
mid = floor( (low + high) / 2 )
|
|
cmp = compare(s[mid], val)
|
|
if cmp > 0 then
|
|
return binary_search(s, val, low, mid-1)
|
|
elsif cmp < 0 then
|
|
return binary_search(s, val, mid+1, high)
|
|
else
|
|
return mid
|
|
end if
|
|
end if
|
|
end function
|