iframe-proxy | Sunbelt Computer Software

History

53 lines (44 loc) · 1.21 KB

Raw

"""

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)

"""

from typing import List

def peak(lst: List[int]) -> int:

"""

Return the peak value of `lst`.

>>> peak([1, 2, 3, 4, 5, 4, 3, 2, 1])

>>> peak([1, 10, 9, 8, 7, 6, 5, 4])

>>> peak([1, 9, 8, 7])

>>> peak([1, 2, 3, 4, 5, 6, 7, 0])

>>> peak([1, 2, 3, 4, 3, 2, 1, 0, -1, -2])

"""

# middle index

m = len(lst) // 2

# choose the middle 3 elements

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

# if middle element is peak

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

return three[1]

# if increasing, recurse on right

elif three[0] < three[2]:

if len(lst[:m]) == 2:

m -= 1

return peak(lst[m:])

# decreasing

else:

if len(lst[:m]) == 2:

m += 1

return peak(lst[:m])

if __name__ == "__main__":

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

peak.py

Latest commit

History

peak.py

File metadata and controls