45 lines
928 B
Plaintext
45 lines
928 B
Plaintext
\\ binary search
|
|
const N=10
|
|
Dim A(0 to N-1)
|
|
A(0):=1,2,3,4,5,6,8,9,10,11
|
|
Print Len(A())=10
|
|
Function BinarySearch(&A(), aValue) {
|
|
def long mid, lo, hi
|
|
def boolean ok=False
|
|
let lo=0, hi=Len(A())-1
|
|
While lo<=hi
|
|
mid=(lo+hi)/2
|
|
if A(mid)>aValue Then
|
|
hi=mid-1
|
|
Else.if A(mid)<aValue Then
|
|
lo=mid+1
|
|
Else
|
|
=mid
|
|
ok=True
|
|
exit
|
|
End if
|
|
End While
|
|
if not ok then =-lo-1
|
|
}
|
|
For i=0 to 12
|
|
Rem Print "Search for value:";i
|
|
where= BinarySearch(&A(), i)
|
|
if where>=0 then
|
|
Print "found i at index: ";where
|
|
else
|
|
where=-where-1
|
|
if where<len(A()) then
|
|
Print "Not found, we can insert it at index: ";where
|
|
Dim A(len(A())+1) ' redim
|
|
stock A(where) keep len(A())-where-1, A(where+1) 'move items up
|
|
A(where)=i ' insert value
|
|
Else
|
|
Print "Not found, we can append to array at index: ";where
|
|
Dim A(len(A())+1) ' redim
|
|
A(where)=i ' insert value
|
|
End If
|
|
end if
|
|
next i
|
|
Print Len(A())=13
|
|
Print A()
|