# To find a local minimum in a field

1. Dec 4, 2005

### alejandrito

Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A 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

2. Dec 13, 2005

### franznietzsche

I haven't tried working this out in detail, but with a clever conditional control statement for the loop you should be able to find a local min testing only every other value, rather than every value(using I=I+2). I think. I might be wrong, but it may be worth a try.

3. Dec 14, 2005

### DrGreg

Hint: does http://en.wikipedia.org/wiki/Divide-and-conquer_algorithm" [Broken] mean anything to you?

(Sorry, franznietzsche's idea doesn't solve the problem because O(n/2) is still O(n).)

Last edited by a moderator: May 2, 2017