# 寻找峰值

描述

给定一个长度为 `n` 的整数数组 `nums`，其具有以下特点：

* 相邻位置的数字是不同的
* `nums` 至少存在一个峰值

假定 **P** 是峰值的位置则满足 `nums[P] > nums[P-1]` 且 `nums[P] > nums[P+1]`，返回数组中任意一个峰值的位置。

* $$1≤nums.length≤10001≤nums.length≤1000$$
* $$−231≤nums\[i]≤231−1−231≤nums\[i]≤231−1$$
* **数组保证至少存在一个峰**
* 如果数组存在多个峰，返回其中任意一个就行
* 数组至少包含 **3** 个数

样例

**样例 1：**

输入：

```
A = [1, 2, 1, 3, 4, 5, 7, 6]
```

输出：

```
1
```

解释：

返回任意一个峰顶元素的下标，6也同样正确。\
**样例 2：**

输入：

```
A = [1,2,3,4,1]
```

输出：

```
3
```

解释：

返回峰顶元素的下标。

挑战

时间复杂度$$O(logN)O(logN)$$

分析：

* **选择中点：** 首先，选择数组的中间位置mid。
* **比较中点与其右邻居：**
  * 如果 nums\[mid]>nums\[mid+1]，说明峰值在中点左边或者中点本身是峰值，因为在这种情况下，左侧肯定有一个上升趋势（包括中点本身）。
  * 如果 nums\[mid]\<nums\[mid+1]，说明峰值在中点右边，因为右侧有一个上升趋势，这意味着峰值必定在右边。
* **缩小搜索范围：** 根据上述比较结果，我们可以缩小搜索区间至中点左边或右边，继续用二分法搜索，直到找到一个峰值。

```python
from typing import (
    List,
)

class Solution:
    """
    @param a: An integers array.
    @return: return any of peek positions.
    """
    def find_peak(self, a: List[int]) -> int:
        # write your code here
        start, end = 0, len(a) - 1

        while start + 1 < end:
            mid = (start + end) // 2
            if a[mid-1] < a[mid] > a[mid+1]:
                return mid
            elif a[mid] < a[mid + 1]:
                start = mid 
            else:
                end = mid
            
```