我尝试了一个在线挑战,问题如下:
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)]
经过优化的变型-在大多数情况下,速度是原来的两倍:
我用下面的输入2 3 4 5 5 8来尝试你的代码,答案应该是8但是答案是5我发布了一个图片,里面有几个测试用例
我想你不能在未排序的数组上运行二进制搜索
代码还为排序数组提供了大量异常列表
为什么不使用
max()
方法??在max(lst)
将返回列表中的最大值相关问题 更多 >
编程相关推荐