在数组中查找局部最小值

给定整数数组，找到局部最小值。如果A [i-1]> A [i]并且A [i] <A [i + 1]，其中i = 1 … n-2，则元素A

[i]被定义为局部最小值。对于边界元素，该数字必须小于其相邻数字。

我知道如果只有一个局部最小值，那么我们可以通过修改后的二进制搜索来求解。但是，如果知道阵列中存在多个局部最小值，可以及时解决O(log n)吗？

如果不能保证数组元素是不同的，则不可能在O（log n）时间内执行此操作。原因如下：假设您有一个数组，其中所有n>

1个值都相同。在这种情况下，所有元素都不是局部最小值，因为没有一个元素少于其邻居。但是，为了确定所有值都相同，您将必须查看所有数组元素，这需要O（n）时间。如果您使用的时间少于O（n），则不必查看所有数组元素。

另一方面，如果保证数组元素是不同的，则可以使用以下观察结果在O（log n）时间内解决此问题：

如果有多个元素，请查看中间元素。如果这是本地最低要求，那么您就完成了。否则，它旁边的至少一个元素必须小于它。现在，想象一下，如果从较小的元素之一开始，然后朝着远离中间元素的方向逐渐移向数组的一端之一，将会发生什么。在每个步骤中，下一个元素要么小于前一个元素，要么将更大。最终，您将以这种方式到达数组的末尾，或者达到局部最小值。请注意，这意味着您这样做是为了找到局部最小值。但是，我们实际上不会这样做。相反，我们将使用在数组的这一部分中存在局部最小值的事实作为丢弃该数组一半的理由。剩下的，我们保证找到一个局部最小值。

因此，您可以构建以下递归算法：

请注意，这具有重复关系

T（1）≤1
T（2）≤1
T（n）≤T（n / 2）+ 1

使用Master定理，可以证明该算法根据需要在O（log n）的时间运行。

希望这可以帮助！

另请注意，只有当数组的边缘小于相邻元素时，该算法才算作局部最小值，此算法才起作用。