在数组中查找局部最小值

如果不能保证数组元素是不同的，则不可能在O（log n）时间内执行此 *** 作。原因如下：假设您有一个数组，其中所有n>
1个值都相同。在这种情况下，所有元素都不是局部最小值，因为没有一个元素少于其邻居。但是，为了确定所有值都相同，您将必须查看所有数组元素，这需要O（n）时间。如果您使用的时间少于O（n），则不必查看所有数组元素。

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

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

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

1. 如果只有一个数组元素，那是局部最小值。
2. 如果有两个数组元素，请检查每个。一个必须是本地最小值。
3. 否则，请查看数组的中间元素。如果是局部最小值，则将其返回。否则，至少一个相邻的值必须小于此值。递归到包含较小元素的数组的一半（而不是中间）。

请注意，这具有重复关系

T（1）≤1

T（2）≤1

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

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

希望这可以帮助！

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