Binary search: Difference between revisions

=={{header|BASIC256}}==

====Recursive Solution====

<lang BASIC256>function binarySearchR(array, valor, lb, ub)

if ub < lb then

return false

else

mitad = floor((lb + ub) / 2)

if valor < array[mitad] then return binarySearchR(array, valor, lb, mitad-1)

if valor > array[mitad] then return binarySearchR(array, valor, mitad+1, ub)

if valor = array[mitad] then return mitad

end if

end function</lang>

====Iterative Solution====

<lang BASIC256>function binarySearchI(array, valor)

lb = array[?,]

ub = array[?]

while lb <= ub

mitad = floor((lb + ub) / 2)

begin case

case array[mitad] > valor

ub = mitad - 1

case array[mitad] < valor

lb = mitad + 1

else

return mitad

end case

end while

return false

end function</lang>

'''Test:'''

<lang BASIC256>items = 10e5

dim array(items)

for n = 0 to items-1 : array[n] = n : next n

t0 = msec

print binarySearchI(array, 3)

print msec - t0; " millisec"

t1 = msec

print binarySearchR(array, 3, array[?,], array[?])

print msec - t1; " millisec"

end</lang>

{{out}}

<pre>3

839 millisec

3

50 millisec</pre>