如果不能保证数组元素是不同的,则不可能在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)的时间运行。
希望这可以帮助!
另请注意,只有当数组的边缘小于相邻元素时,该算法才算作局部最小值,此算法才起作用。