Cassidoo 2020-10-05

find_pivot_point.py

question = """
Given an array that was once sorted in ascending order is rotated at some 
pivot unknown to you beforehand (so [0,2,4,7,9] might become [7,9,0,2,4], for 
example). Find the minimum value in that array in O(n) or less.
"""

def find_pivot_point(a):
    start = 0
    end = len(a) - 1
    mid = int((start + end) / 2)

    O_n = 0

    while True:
        if start == mid or mid == end:
            O_n += 1
            return(end if a[start] > a[end] else start, O_n)
        else:
            if a[start] > a[mid]:
                O_n += 1
                end = mid
            elif a[mid] > a[end]:
                O_n += 1
                start = mid
            mid = int((start + end) / 2)

a = [ 7, 9, 0, 2, 4 ]

pivot_point, O_n = find_pivot_point(a)
print('minimum value = {} at position {}'.format(a[pivot_point], pivot_point))
print('n = ' + str(len(a)) + '; O(n) = ' + str(O_n))