binarySearch.frink

Download or view 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]
}


Download or view 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 20145 days, 19 hours, 57 minutes ago.