# binarySearch.frink

``` // 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] } ```

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 19023 days, 9 hours, 16 minutes ago.