Restored from previous forum. Originally posted by Andre.
Code: Select all
;- Information
; This little routine is a BB conversion
; for fast searching in large sorted arrays (containing numeric values)
; done by Andre (andre@purebasic.com)
; 5. April 2003
;- Declare variables
high=0 ; high element of search
low=0 ; low element of search
middle=0 ; middle value of search
oldmiddle=0 ; used to check if the value couldn't be found
value=0 ; the value to search for
asize=0 ; the size of the array
done=0 ; flag to see if we have finished the search
;- Settings
show.b = 0 ; if value = 1, then all array values are printed to the console window, else not
;- OpenConsole
OpenConsole()
;- Get informations
Print("How many elements would you like in the array?: ")
asize=Val(Input())
low=0
high=asize-1
PrintN("")
Print("What value would you like to search for in the array?: ")
value=Val(Input())
PrintN("")
;- Security check
If asize=0 Or value=0
PrintN("Value(s) are missing, program will exit...")
Input()
End
EndIf
;- Build array values
Dim array(asize) ; dim the array to be searched
; the following routine does fill the array with precalculated values, change this to your own loading routine etc.
For i=0 To asize-1 ; fill the array from first to last element, for filling backwards use this code: For i=asize-1 To 0 Step -1
array(i)=i*(2+i) ; fill each element with a strange number, change it to whatever you want
If show = 1
PrintN("Value of array("+Str(i)+") is: "+Str(array(i))) ; list all the values
EndIf
Next
;- Search routine
PrintN("Searching for "+Str(value))
Repeat
middle=(high + low) / 2 ; find the middle value
PrintN("Middle is "+Str(array(middle))) ; print the value of middle for 'debug' purposes
If oldmiddle=middle ; If oldmiddle has equaled middle for more than one loop, then we know that the element couldn't be found
PrintN("The value is not stored in any element in this array")
done=1 ; tell the loop that we are done and to leave
EndIf
oldmiddle=middle ; store a value for oldmiddle, used to see if we couldn't find the value
If array(middle)=value
PrintN("Found it in element "+Str(middle)) ; found the value
EndIf
If valuearray <> (middle)
low=middle ; or if the middle is too low, then reset low to middle
EndIf
Until array(middle)=value Or done=1 ; loop until the middle value is equal to the value we specified or done is true
;- Finish program
PrintN("Press return...")
Input()
CloseConsole()
Edit: added Tinman's tipps, added value input check
