Amazon 面试题：在无序数组中找到局部最小值

Given an array of integers, find the index of a local minimum.

A local minimum is defined as an element that is strictly smaller than its neighbors.
Formally:

• For any index i,
  A[i] < A[i-1] and A[i] < A[i+1].

You may assume:

• The array has no equal adjacent elements, i.e., A[i] != A[i+1].
• A valid local minimum always exists.
• The array is not necessarily sorted.
• You need to find any one local minimum.

Goal:
Return the index of one such local minimum.

Example:

Input:  [9, 7, 2, 8, 5, 6]
Output: 2   # A[2] = 2 is a local minimum

这道题要求在一个无序数组中找到任意一个“局部最小值”的下标。所谓局部最小值，就是某个元素比它左右两侧的邻居都小。题目保证数组不存在相等的相邻元素，而且至少存在一个局部最小值。

关键思路：

• 因为局部最小一定存在，可以利用“左右两边总有下降趋势”的性质
• 最优解使用 二分查找 O(log n) 来定位局部最小值

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。