Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A(adsbygoogle = window.adsbygoogle || []).push({}); is called a local minimum if A[I-1] >= A<= A[I+1]. Find an alogrithm that will find some local minimum in a time asymptotically better then O(n). Hint: Consider that in each field deffined as before there must exist at least one local minimum.

The best algorithm (or programme in Pascal) I´ve found is the following:

......

while (A[I+1] > A[I+2] and I<N-1) do I:=I+1;

LOCMIN:=A[I+1];

.....

which needs maximally N-1 steps to find a local minimum, but this is not enough if we want the asymptotical difficulty better then O(n). Could anybody help me with improving the algorithm? Thanks

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# To find a local minimum in a field

Loading...

Similar Threads for find local minimum | Date |
---|---|

Can't find my Localhost Database Engine for SQL Server | Feb 16, 2018 |

C/++/# Finding duplicates algorithm | Jan 20, 2018 |

Copying from /usr/local/bin to /usr/bin? | Sep 21, 2017 |

C/++/# Is there an easy way to find ints i,j,k satisfying i*j=k^2? | May 19, 2017 |

C/++/# Program to find combination of letters associated with phone | Mar 1, 2017 |

**Physics Forums - The Fusion of Science and Community**