#P0050. 寻找峰值

寻找峰值

题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给定一个长度为 nn 的数列 {a}\{a\} ,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 a−1=an=−∞ a_{-1} = a_n = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

输入格式

第一行包含一个整数 n (1 ≤ n ≤ 1000) —— 数组中的元素个数。

第二行包含 n 个整数 k,表示数列中的元素。( −231≤k≤231−1-2^{31} ≤ k ≤ 2^{31} - 1 )

输出格式

输出峰值元素的索引。

样例 #1

样例输入 #1

4
1 2 3 1

样例输出 #1

2

解释:3 是峰值元素,你的函数应该返回其索引 2。

样例 #2

7
1 2 1 3 5 6 4

样例输出 #2

1

或

5

解释:你的函数可以返回索引 1,其峰值元素为 2;或者返回索引 5,其峰值元素为 6。

提示

  • 对于所有有效的 i 都有 ai!=ai+1a_{i} != a_{i+1}