Thursday, March 8, 2012

Find the maximum in an array increasing and than decreasing

Can you make this better than linear?
Pubblicato da a
Reazioni: 

1 comment:

  1. dichotomize: if current range is [m M], find if mid=(m+M)/2 is on the increasing side or decreasing side.
    To that effect, lookup the elements following 'mid' position and see if they are increasing or decreasing.
    If increasing, m = mid. Otherwise M = mid.

    -> log(N), without any real worse case actually.

    ReplyDelete

Subscribe to: Post Comments (Atom)