Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: To find a local minimum in a field

  1. Dec 4, 2005 #1
    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;
    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. jcsd
  3. Dec 4, 2005 #2


    User Avatar

    Staff: Mentor

    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....
  4. Dec 5, 2005 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook