寻找峰值

题目描述

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

给定一个整数数组 nums，请找到一个峰值元素并返回其下标。数组中可能包含多个峰值，返回任意一个峰值所在位置即可。

你可以假设：

• nums[-1] = -∞
• nums[n] = -∞

其中 n 是数组长度。

你需要设计并实现时间复杂度为 O(log n) 的算法。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数，表示数组 nums。

输出格式

输出一个整数，表示任意一个峰值元素的下标。

数据范围

1 <= n <= 1000

-2^31 <= nums[i] <= 2^31 - 1

保证对所有有效的 i，都有 nums[i] != nums[i + 1]。

样例 1

输入

4
1 2 3 1

输出

2

样例 2

输入

7
1 2 1 3 5 6 4

输出

5

说明

输出 1 也是正确答案，因为下标 1 和下标 5 都是峰值位置。