python - 在先递减然后递增且可能包含重复项的列表中查找最小值

Question

给定一个列表，该列表可以分为两部分 L[:z] 和 L[z:]，其中第一部分是非递增的，第二部分是非递减的，并且可能包含也可能不包含重复元素，创建一个功能使得:

---

输入:

• 上面指定的列表L
• 一个值 k 表示任何给定值在列表中重复的最大次数

输出:

• 列表的最小值

复杂性和要求

• O(log n)
• 只能使用不包括 min/max 的内置库函数

---

我有以下内容:

def findmin(L, k = None):
    left = 0
    right = len(L)-1
    foundmin = False

    while not foundmin:
        mp = (left + right)//2
        if L[mp] > L[mp+1]:
            left = mp
        elif L[mp-1] < L[mp]:
            right = mp+1
        else:
            return L[mp]

它仅适用于某些列表，例如: L = [9,9,4,3,2,1,7,7,10,10]

但它不能正确处理列表，例如: L = [6,5,4,3,3,3,3,3,3,3,3,3,1,7,7,7,7]

我曾尝试修改函数以容纳重复的元素，但无济于事。我也没有看到该函数的输入 k 的效用。想法？

Answer 1

此代码在 O(logn) 中运行并且没有使用 k 参数。

这是某种二进制搜索，就像@coldspeed 评论的那样。

def find_min(l, k=None):
    left = 0
    right = len(l) - 1
    while left <= right:
        middle = (left + right) // 2
        if l[middle] < l[left] or (l[middle] == l[left] and middle > left):
            left = middle
        elif l[middle] < l[right] or (l[middle] == l[right] and middle < right):
            right = middle
        else:
            return l[middle]