almost unimodal maximum problem

import math

#generate a nearly worst-case list, where the max is at the end of the list after a long slope downward.

height = 100000;
base = 200;
array = [height+base+1];

for i in range(height):
    array.append(height-i+base);
    
array.append(height+base-2);
array.append(height+base+2);
array.append(height+base+4);
array.append(height+base+3);

n = len(array)
steps = 0

# there are 4 types of node in a unimodal list: decreasing, minimum, increasing, and maximum.

# there are two sections of 'decreasing' in an almost unimodal list: from the max, and from the first node.

# the first node of an almost unimodal list is either the maximum, or not the maximum. a valuable tautology.

# if this first element is also less than the last element, then the list may be the y coordinates of
# an unordered list of vertices in a convex polygon.

# the first decreasing section is not connected to the maximum, while the second is always connected to it.

# therefore if we hit a node that is below the first node, it must be left of the maximum.

notmax = array[0]

depth = 2
current = math.floor(n / depth)
left = current - 1
right = current + 1
found = 0

# initialization, start in the middle of the list, not a bad guess.

while (found == 0):
    steps += 1
    found = 1
        
    # if the right of the current index is larger, then the maximum must be that way.
    # go right (add) one half as far as we went last time. not max, so found is 0.
    if (array[int(right)] > array[int(current)] or (array[int(left)] > array[int(current)] and notmax > array[int(current)])):
        if (n / depth > 1):
            depth *= 2
            current += math.floor(n / depth)
        else:
            current += 1
            
        left = current - 1
        right = current + 1
        found = 0

# if the left of the current index is larger, then the maximum must be that way.
    # go left (subtract) one half as far as we went last time. not max, so found is 0.
    if (array[int(left)] > array[int(current)] and notmax < array[int(current)]):
        if (n / depth > 1):
            depth *= 2
            current -= math.floor(n / depth)
        else:
            current -= 1
            
        left = current - 1
        right = current + 1
        found = 0

print "max: ", array[int(current)], " steps: ", steps, " entries: ", n

# works only for truly unimodal lists, not lists with multiple terms of the same value adjacent each other.

Python Fiddle

Python Cloud IDE