52 lines
1.5 KiB
Rexx
52 lines
1.5 KiB
Rexx
data = .array~of(1, 3, 5, 7, 9, 11)
|
|
-- search keys with a number of edge cases
|
|
searchkeys = .array~of(0, 1, 4, 7, 11, 12)
|
|
say "recursive binary search"
|
|
loop key over searchkeys
|
|
pos = recursiveBinarySearch(data, key)
|
|
if pos == 0 then say "Key" key "not found"
|
|
else say "Key" key "found at postion" pos
|
|
end
|
|
say
|
|
say "iterative binary search"
|
|
loop key over searchkeys
|
|
pos = iterativeBinarySearch(data, key)
|
|
if pos == 0 then say "Key" key "not found"
|
|
else say "Key" key "found at postion" pos
|
|
end
|
|
|
|
::routine recursiveBinarySearch
|
|
-- NB: Rexx arrays are 1-based
|
|
use strict arg data, value, low = 1, high = (data~items)
|
|
|
|
-- make sure we don't go beyond the bounds
|
|
high = min(high, data~items)
|
|
-- zero indicates not found
|
|
if high < low then return 0
|
|
|
|
mid = (low + high) % 2
|
|
if data[mid] > value then
|
|
return recursiveBinarySearch(data, value, low, mid - 1)
|
|
else if data[mid] < value then
|
|
return recursiveBinarySearch(data, value, mid + 1, high)
|
|
-- got it!
|
|
return mid
|
|
|
|
::routine iterativeBinarySearch
|
|
-- NB: Rexx arrays are 1-based
|
|
use strict arg data, value, low = 1, high = (data~items)
|
|
|
|
-- make sure we don't go beyond the bounds
|
|
high = min(high, data~items)
|
|
-- zero indicates not found
|
|
if high < low then return 0
|
|
loop while low <= high
|
|
mid = (low + high) % 2
|
|
if data[mid] > value then
|
|
high = mid - 1
|
|
else if data[mid] < value then
|
|
low = mid + 1
|
|
else
|
|
return mid
|
|
end
|
|
return 0
|