finding the peak of a unimodal list using divide and conquer a unimodal array is defined as follows array is increasing up to index p then decreasing afterwards for p 1 an obvious solution can be performed in on to find the maximum of the array from kleinberg and tardos algorithm design addison wesley 2006 chapter 5 solved exercise 1 return the peak value of lst peak1 2 3 4 5 4 3 2 1 5 peak1 10 9 8 7 6 5 4 10 peak1 9 8 7 9 peak1 2 3 4 5 6 7 0 7 peak1 2 3 4 3 2 1 0 1 2 4 middle index choose the middle 3 elements if middle element is peak if increasing recurse on right decreasing return the peak value of lst peak 1 2 3 4 5 4 3 2 1 5 peak 1 10 9 8 7 6 5 4 10 peak 1 9 8 7 9 peak 1 2 3 4 5 6 7 0 7 peak 1 2 3 4 3 2 1 0 1 2 4 middle index choose the middle 3 elements if middle element is peak if increasing recurse on right decreasing
from __future__ import annotations


def peak(lst: list[int]) -> int:
    
    
    m = len(lst) // 2

    
    three = lst[m - 1 : m + 2]

    
    if three[1] > three[0] and three[1] > three[2]:
        return three[1]

    
    elif three[0] < three[2]:
        if len(lst[:m]) == 2:
            m -= 1
        return peak(lst[m:])

    
    else:
        if len(lst[:m]) == 2:
            m += 1
        return peak(lst[:m])


if __name__ == "__main__":
    import doctest

    doctest.testmod()