Skip to main content
 首页 » 编程设计

python之查找数组中的最大元素,先升序再降序

2024年10月24日16lexus

我尝试了一个在线挑战,其中有一个问题如下:

You are given an array which increases at first and then starts decreasing. For example: 2 3 4 5 6 7 8 6 4 2 0 -2. Find the maximum element of these array.

以下是我使用二进制搜索的代码,它在 O(log(n)) 中给出了正确答案,但我不知道是否有更好的解决方案。 谁能帮我解决这个问题?

a= map(int, raw_input().split()) 
def BS(lo,hi): 
    mid = lo+ (hi-lo)/2 
    if a[mid]>=a[mid+1]: 
        if a[mid]>a[mid-1]: 
            return mid 
        else: 
            return BS(lo,mid) 
    else: 
        return BS(mid,hi) 
 
print a[BS(0,len(a)-1)] 

请您参考如下方法:

一个优化的变体——在大多数情况下快两倍:

# ® Видул Николаев Петров 
a = [2, 3, 4, 5, 6, 7, 8, 10, 12, 24, 48, 12, 6, 5, 0, -1] 
 
def calc(a): 
    if len(a) <= 2: 
        return a[0] if a[0] > a[1]  else a[1] 
 
    l2 = len(a) / 2 
 
    if a[l2 + 1] <= a[l2] and a[l2] >= a[l2 - 1]: 
        return a[l2] 
 
    if a[l2] > a[l2 + 1]: 
        return calc(a[:l2+1]) 
    else: 
        return calc(a[l2:]) 
 
print calc(a) # 48