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**

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**