// 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 // (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