题目地址：

https://www.lintcode.com/problem/peak-index-in-a-mountain-array/description

给定一个长度大于等于$3$的数组$A$，题目保证存在某个下标$i$满足$0<i<l_A-1$使得$A[0]<A[1]<...<A[i-1]<A[i]>A[i+1]>...>A[l_A-1]$。找到那个$i$。

思路是二分。我们需要找到最后一个满足$A[i]>A[i-1]$的那个$i$。代码如下：

public class Solution { /** * @param A: an array * @return: any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] */ public int peakIndexInMountainArray(int[] A) { // Write your code here int l = 1, r = A.length - 1; while (l < r) { int m = l + (r - l + 1 >> 1); if (A[m] > A[m - 1]) { l = m; } else { r = m - 1; } } return l; } }

时间复杂度$O(\log l_A)$，空间$O(1)$。