minvalley.py

# Logic:
#   a > b --> discard everything to the left of a
#   a < b --> discard everything to the right of b
#   a = b = c --> we know that either
#     a) all elements between a and b are all equal to b, or
#     b) all elements between b and c are all equal to b.
#     time for a linear search.
 
def minvalley(xs, l, r):
   while True:
      (ml, m, mr) = ((2*l+r)/3, (l+r)/2, (l+2*r)/3)
      if r-l < 6 or xs[ml] == xs[m] and xs[m] == xs[mr]:
         return min(xs[l:r+1])
      if xs[ml] >= xs[mr]: # this implies xs[ml] > xs[m] or xs[m] > xs[mr]
         l = ml
      if xs[ml] <= xs[mr]: # this implies xs[ml] < xs[m] or xs[m] < xs[mr]
         r = mr