Re: Find Max of "Concave" List
- To: mathgroup at smc.vnet.net
- Subject: [mg12991] Re: [mg12918] Find Max of "Concave" List
- From: "Jrgen Tischer" <jtischer at col2.telecom.com.co>
- Date: Sun, 28 Jun 1998 02:52:13 -0400
- Sender: owner-wri-mathgroup at wolfram.com
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
>
>