binarySearch.frink

View or download binarySearch.frink in plain text format


// This is an algorithm for doing binary search of a list in Frink.
//
// arguments:
//    list:          an ordered list of items
//
//    item:          the item to search for in the list
//
//    orderFunction: a two-argument function of the form {|a,b| ... } where
//                   the function returns -1 if a<b, 0 if a==b, and 1 if a > b
//                   (such as the <=> operator returns.  This is the default
//                    comparison if no order function is passed in.)
//
// This returns the index of the item to insert *before* (for example,
// using the method list.insert[pos, item] ) to put the item in the right
// order.  If the item is found anywhere in the list, this returns the index
// of the matching item in the list.  If the item is not found in the
// list, this still returns the index before which it should be inserted.

binarySearch[list, item, orderFunction = {|a,b| a <=> b}] :=
{
   start = 0
   end = length[list] - 1
   var current
   var comp

   while (start <= end)
   {
      current = (end + start) div 2
      comp = orderFunction[item, list@current]

      if comp == 0
         return current

      if (comp == -1)
         end = current - 1
      else
         start = current + 1
   }

   return start
}


View or download binarySearch.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17591 days, 17 hours, 40 minutes ago.