To find a local minimum in a field

[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.

 

[berkeman]

Do we know the field is monotonic approaching the minimum from both directions, with only one minimum? If so, then use a binary search to bounce back and forth across the minimum and home in on it. Maybe even estimate how far away the minimum is by the slop of a couple of samples, and jump to the expecte location and do the same slope calculation and jump again...

 

[alejandrito]

The field shouldn´t be monotonic necessarilly, but it seems that any using of binary search could reduce sufficiently the number of steps. I will have a look on your hints, thanks.