MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Find Max of "Concave" List


Hi Chris,
not elegant, but quite fast: bisection:

concaveMax[li_]:= Module[{a=1,b=Length[li]},
          While[b-a>1,
            With[{n=Quotient[b+a,2]},
                If[li[[n]]==li[[n+1]],Return[li[[n]]]];
                If[li[[n]]<li[[n+1]],a=n+1,b=n]]];
          Max[li[[a]],li[[b]]]]

J=FCrgen

-----Original Message-----
From: Chris Farr <farr at brown.edu>
To: mathgroup at smc.vnet.net
Subject: [mg12991] [mg12918] Find Max of "Concave" List


>
>I have a one-dimensional list which is concave.  That is, if you did a
>ListPlot on the list you would have a concave curve.
>
>Given the concavity, when finding the max, it is inefficient to use
>Max[] which does a comparison on all elements of the list.
>
>Is there an elegant way to exploit the concavity when performing a
>Max[]?  That is, the algorithm should stop when the next element in the
> list is lower then the previous element.  This would limit the number
>of  comparisons.
>
>Thanks,
>
>Chris Farr
>
>



  • Prev by Date: Re: Strange behavior of Sort
  • Next by Date: Re: Inconsistencies in pattern matching.
  • Previous by thread: Re: Find Max of "Concave" List
  • Next by thread: Re: Find Max of "Concave" List