October 17, 2021, 10:09:40

Author Topic: [bb] Binary Search by dirkduck [ 1+ years ago ]  (Read 596 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Binary Search by dirkduck [ 1+ years ago ]
« on: June 29, 2017, 00:28:41 »
Title : Binary Search
Author : dirkduck
Posted : 1+ years ago

Description : A binary search is a faster method of searching a sorted array than directly checking each element for a value.  Binary searches simply check the value of the middle element in an array, check if its value is higher or lower than the target
value, then cut the array in half again.  The search keeps cutting the "tree" in half, resulting in a very fast search for a value in an array with a large number of elements.  Enjoy!  

                Chris Rowland
                chris@...
                <a href="http://www.labino.net/" target="_blank">http://www.labino.net[/url]


Code :
Code: BlitzBasic
  1. Graphics 640,480,16,2
  2.  
  3.  
  4. high=0 ;high element of search
  5. low=0 ;low element of search
  6. middle=0 ;middle value of search
  7. oldmiddle=0 ;used to check if the value couldn't be found
  8. value=0 ;the value to search for
  9. asize=0 ;the size of the array
  10. done=0 ;flag to see if we have finished the search
  11.  
  12.  
  13. ;gather info
  14. asize=Input("How many elements would you like in the array?: ")
  15. low=0
  16. high=asize-1
  17.  
  18. value=Input("What value would you like to search for in the array?: ")
  19.  
  20.  
  21. Dim array(asize) ;dim the array to be searched
  22.  
  23. For i=0 To asize-1
  24.         array(i)=i*(2+i)   ;fill each element with a strange number, change it to whatever you want
  25.         Print "value of array("+Str$(i)+") is: "+Str$(array(i)) ;list all the values
  26. Next
  27.  
  28. Print "Searching for "+Str$(value)
  29.  
  30. Repeat
  31.         middle=(high - low)/2 + low ;find the middle value
  32.         Print "middle is "+Str$(array(middle))  ;print the value of middle for 'debug' purposes
  33.        
  34.         If(oldmiddle=middle) ;If oldmiddle has equaled middle For more Then 1 loop Then we know that the element couldn't be found
  35.                 Print "The value is not stored in any element in this array"
  36.                 done=1  ;tell the loop that we are done and to leave
  37.         EndIf
  38.  
  39.         oldmiddle=middle ;store a value for oldmiddle, used to see if we couldn't find the value
  40.        
  41.         If(array(middle)=value) Print "found it in element "+Str$(middle) ;found the value
  42.         If(value<array(middle)) Then high=middle ;if the middle is too high Then reset high to middle
  43.         If(value>array(middle)) Then low=middle ;or if the middle is too low then reset low to middle
  44.  
  45.  
  46. Until ((array(middle)=value)Or(done=1)) ;loop until the middle value is equal to the value we specified or done is true
  47.  
  48. WaitKey()


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal