divide_and_conquer.peak

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 O(n), to find the maximum of the array. (From Kleinberg and Tardos. Algorithm Design. Addison Wesley 2006: Chapter 5 Solved Exercise 1)

Functions

peak(→ int)

Return the peak value of lst.

Module Contents

divide_and_conquer.peak.peak(lst: list[int]) → int

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