我希望找到列表中元素先减少后增加的最小元素

Question

我想在O(log n) complexity中实现它。使用binary search的思想可以实现它。我是这样说的：让我是一个列表；L= [12,10,9,7,6,5,8,9,11]所以预期的结果应该是5。在python中是否有一个简单的算法来实现它？你知道吗

def binse(l,lo,hi):
    n =len(l)
    lo = 0
    hi =n
    mid =(lo+hi)//2
    if (hi-lo)<2:
       return lo
    if l[mid]<l[mid-1] and l[mid]<l[mid+1]:
       return l[mid]
    elif l[mid]<l[mid-1] and l[mid]>l[mid+1]:
       return binse(l,mid+1,hi)
    elif l[mid]>l[mid-1] and l[mid]<l[mid+1]:
       return binse(l,lo,mid)
    else:
       return

l = [13,11,5,6,7,8,9,11,13]
lo =0
hi =len(l)
print(binse(l,lo,hi))

Answer 1

你说的-用二进制搜索。在每个探针上，取两个连续的条目并确定值是增加还是减少。基于此，你知道该进一步细分哪个地区。你知道吗

顺便说一句，我忽略了平等的问题

根据发布的代码更新：

1. binse做的第一件事就是覆盖lo和hi参数-糟糕！你知道吗
2. return lo行显然是错误的，因为它没有返回数组值
3. 在某些边缘情况下需要小心一点，包括接近端点以及具有相等值序列时
4. 最后的“回归”也显然是错误的，因为它没有任何价值。你知道吗

第一项是您看到无限递归的原因。你知道吗

Answer 2

def mini(lis):
s, e = 0, len(lis)-1
while True:
    m = (s+e)/2
    if lis[m] > lis[m+1]:
        s = m
    elif lis[m-1] < lis[m]:
        e = m+1
    else:
        return m

这应该管用。你知道吗