binarySearch.frink

View or download binarySearch.frink in plain text format


// This is an algorithm for doing binary search of a list in Frink.
//
// This is now obsolete.  The class OrderedList in Frink will do this
// for you and contains a .binarySearch method.
//
// 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
}

/** This is a function that tries to find a single local extreme of a function.
    It uses a binary search routine.

    args:
     [f, xmin, xmax, minxstep, multiplier]

    where:
      f is a function that takes one argument for x and returns a single value.
      xmin is the minimum of the range to search
      xmax is the maximum of the range to search
      minxstep is the smallest x step to take.
      multiplier is 1 to find minimum, -1 to find maximum.
*/

findAnExtreme[f, xmin, xmax, minxstep, multiplier] :=
{
   do
   {
      // We use this formulation so it works with dates.
      mid = xmin + (xmax - xmin) / 2

      fmin = f[xmin] multiplier
      fmax = f[xmax] multiplier
      if fmin < fmax
         xmax = mid
      else
         xmin = mid
   } while xmax - xmin > minxstep

   if fmin<fmax
      return [xmin, fmin multiplier]
   else
      return [xmax, fmax multiplier]
}


/** This is a function that tries to find a single local minimum of a function.
    It uses a binary search routine.

    args:
     [f, xmin, xmax, minxstep]

    where:
      f is a function that takes one argument for x and returns a single value.
      xmin is the minimum of the range to search
      xmax is the maximum of the range to search
      minxstep is the smallest x step to take.
*/

findALocalMinimum[f, xmin, xmax, minxstep] :=
{
   return findAnExtreme[f, xmin, xmax, minxstep, 1]
}



/** This is a function that tries to find a single local maximum of a function.
    It uses a binary search routine.

    args:
     [f, xmin, xmax, minxstep]

    where:
      f is a function that takes one argument for x and returns a single value.
      xmin is the minimum of the range to search
      xmax is the maximum of the range to search
      minxstep is the smallest x step to take.
*/

findALocalMaximum[f, xmin, xmax, minxstep] :=
{
   return findAnExtreme[f, xmin, xmax, minxstep, -1]
}


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 18926 days, 8 hours, 54 minutes ago.