日拱一卒（16）——leetcode学习记录：山脉数组峰值索引
一、题目
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
二、分析
要求是O(log(n))的时间复杂度，那么应该采用二分法。具体是找到最大的元素的一半，直至找到峰顶元素。这里实现的细节值得推敲，包括终止条件、判断条件的设置。
O(log(n))的时间复杂度的理解，假设k次二分后范围缩小到1，那么n/2^k = 1，可以求解k是log2(n)
三、题解
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left,right = 0,len(arr)-1
while left+1 < right:
mid = (left+right)//2
if arr[mid] < arr[mid+1]:
left = mid
else:
right = mid
return right
原文地址：https://blog.csdn.net/m0_72708335/article/details/144460577
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！