Binary search: Difference between revisions
Content added Content deleted
(Add perl version.) |
(Add Seed7 example) |
||
Line 268: | Line 268: | ||
elif l[mid] < value: return binary_search(l, value, mid+1, high) |
elif l[mid] < value: return binary_search(l, value, mid+1, high) |
||
else: return mid |
else: return mid |
||
=={{header|Seed7}}== |
|||
===Iterative=== |
|||
<pre> |
|||
const func integer: binarySearchIterative (in array elemType: arr, in elemType: aKey) is func |
|||
result |
|||
var integer: result is 0; |
|||
local |
|||
var integer: low is 1; |
|||
var integer: high is 0; |
|||
var integer: middle is 0; |
|||
begin |
|||
high := length(arr); |
|||
while result = 0 and low <= high do |
|||
middle := low + (high - low) div 2; |
|||
if aKey < arr[middle] then |
|||
high := pred(middle); |
|||
elsif aKey > arr[middle] then |
|||
low := succ(middle); |
|||
else |
|||
result := middle; |
|||
end if; |
|||
end while; |
|||
end func; |
|||
</pre> |
|||
===Recursive=== |
|||
<pre> |
|||
const func integer: binarySearch (in array elemType: arr, in elemType: aKey, in integer: low, in integer: high) is func |
|||
result |
|||
var integer: result is 0; |
|||
begin |
|||
if low <= high then |
|||
result := (low + high) div 2; |
|||
if aKey < arr[result] then |
|||
result := binarySearch(arr, aKey, low, pred(result)); # search left |
|||
elsif aKey > arr[result] then |
|||
result := binarySearch(arr, aKey, succ(result), high); # search right |
|||
end if; |
|||
end if; |
|||
end func; |
|||
const func integer: binarySearchRecursive (in array elemType: arr, in elemType: aKey) is |
|||
return binarySearch(arr, aKey, 1, length(arr)); |
|||
</pre> |