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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

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

**Physics Forums | Science Articles, Homework Help, Discussion**