78 lines
923 B
Plaintext
78 lines
923 B
Plaintext
'iterative binary search example
|
|
|
|
define size = 0, search = 0, flag = 0, value = 0
|
|
define middle = 0, low = 0, high = 0
|
|
|
|
dim list[2, 3, 5, 6, 8, 10, 11, 15, 19, 20]
|
|
|
|
arraysize size, list
|
|
|
|
let value = 4
|
|
gosub binarysearch
|
|
|
|
let value = 8
|
|
gosub binarysearch
|
|
|
|
let value = 20
|
|
gosub binarysearch
|
|
|
|
end
|
|
|
|
sub binarysearch
|
|
|
|
let search = 1
|
|
let middle = 0
|
|
let low = 0
|
|
let high = size
|
|
|
|
do
|
|
|
|
if low <= high then
|
|
|
|
let middle = int((high + low ) / 2)
|
|
let flag = 1
|
|
|
|
if value < list[middle] then
|
|
|
|
let high = middle - 1
|
|
let flag = 0
|
|
|
|
endif
|
|
|
|
if value > list[middle] then
|
|
|
|
let low = middle + 1
|
|
let flag = 0
|
|
|
|
endif
|
|
|
|
if flag = 1 then
|
|
|
|
let search = 0
|
|
|
|
endif
|
|
|
|
endif
|
|
|
|
loop low <= high and search = 1
|
|
|
|
if search = 1 then
|
|
|
|
let middle = 0
|
|
|
|
endif
|
|
|
|
if middle < 1 then
|
|
|
|
print "not found"
|
|
|
|
endif
|
|
|
|
if middle >= 1 then
|
|
|
|
print "found at index ", middle
|
|
|
|
endif
|
|
|
|
return
|