Binary search: Difference between revisions
Content added Content deleted
(→{{header|UNIX Shell}}: Cosmetic changes) |
|||
Line 2,688: | Line 2,688: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|Phix}}== |
|||
Copied from Euphoria. The low + (high-low)/2 trick is not needed, since interim integer results are accurate to 53 bits (on 32 bit, 64 bits on 64 bit) on Phix. |
|||
===Recursive=== |
|||
<lang Phix>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</lang> |
|||
===Iterative=== |
|||
<lang Phix>function binary_search(sequence s, object val) |
|||
integer low, high, mid, cmp |
|||
low = 1 |
|||
high = length(s) |
|||
while low <= high do |
|||
mid = floor( (low + high) / 2 ) |
|||
cmp = compare(s[mid], val) |
|||
if cmp > 0 then |
|||
high = mid - 1 |
|||
elsif cmp < 0 then |
|||
low = mid + 1 |
|||
else |
|||
return mid |
|||
end if |
|||
end while |
|||
return 0 -- not found |
|||
end function</lang> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |