Binary search of an array for exact or nearest match

This code will allow you to search through a sorted array in the fastest possible manner.

The example code using a simple string array and inserts data into the array to ensure that the array stays sorted.

                                    ` This code was downloaded from The Game Creators
                                    ` It is reproduced here with full permission
                                    ` http://www.thegamecreators.com
                                    
                                    dim SearchArray(20) as string

` Prepare an initial array - don't need to do this, an empty array works fine too
for i=0 to 20
   SearchArray(i) = chr$(i + 65)
next i

repeat

   ` Read a new string
   read InsertString$
   if InsertString$ <> ""

      ` Find the insert position
      Position = BinarySearch( InsertString$, 1 )

      ` If it's past the end of the array, append
      if Position > array count( SearchArray() )
         array insert at bottom SearchArray()
      else
         ` Otherwise, insert
         array insert at element SearchArray(), Position
      endif

      ` Set the new item
      SearchArray(Position) = InsertString$
   endif

until InsertString$ = ""

` Display the array contents
for i=0 to array count( SearchArray() )
   print i, " - ", SearchArray(i)
next
wait key
end

` Some data to insert
data "@ Insert at the front"
data "Z Insert at the end"
data "G Somewhere in the middle"
data "  Insert at the front again"
data "H"
data "I"
data ""



function BinarySearch(Target as string, Nearest as integer)
   local High as integer
   local Low as integer
   local Middle as integer

   ` Set the Low and High points outside of the array
   Low = -1
   High = array count( SearchArray() )+1

   ` Loop while the difference between them is above 1 (ie, they have not passed or matching)
   while High - Low > 1

      ` Pick a nid-point
      Middle = (High + Low) / 2

      ` Test to see if the item is below the target value
      if SearchArray(Middle) < Target

         ` If it is, move the low point to the mid-point
         Low = Middle
      else

         ` Otherwise, move the high point to the mid-point
         High = Middle
      endif
   endwhile

   ` If not looking for a best match, then need to do some further checking
   if Nearest = 0

      ` If the high-point is still beyond the end of the array, exit with a 'not found'
      if High > array count( SearchArray() ) then exitfunction -1

      ` If the item currently pointed to by the high-point is not the one, exit with a 'not found'
      if SearchArray(High) <> Target then exitfunction -1

      ` At this point, we have an exact match
   endif
endfunction High