Dismiss Notice
Join Physics Forums Today!
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

  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 13, 2005 #2
    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.
  4. Dec 14, 2005 #3


    User Avatar
    Science Advisor
    Gold Member

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook