在序列中查找元素 ai 的算法

Question

一个序列 A=[a1, a2,...,an] 是一个谷序列，如果有一个索引 i 1 < i < n 这样:

a1 > a2 > .... > ai 

和

ai < ai+1 < .... < an.

给定一个谷序列必须至少包含三个元素。

我真正感到困惑的是，我们如何找到一个算法来找到元素 ai，如上所述，在 O(log n) 时间？ 它会类似于 O(log n) 二进制搜索吗？

如果我们确实有一个二进制搜索算法，它可以在 O(log n) 时间内找到一个数组的元素，我们可以将运行时间提高到 O(log log n) ?

Answer 1

要拥有 BIG-O(logn) 算法，我们必须在恒定时间内将问题大小减少一半。

具体来说，在这个问题中，我们可以选择一个中点，并检查它的斜率是增加的、减少的还是底部。

• 如果斜率在增加，中点之后的部分可以忽略
• 否则如果斜率下降，则可以忽略中点之前的部分
• 否则中点应该是底部，因此我们找到了我们的目标。

Java 代码示例:

输入:[99, 97, 89, 1, 2, 4, 6]，输出:1

public int findBottomValley(int[] valleySequence) {
    int start = 0, end = valleySequence.length - 1, mid;

    while (start + 1 < end) {
        mid = start + (end - start) / 2;

        if (checkSlope(mid, valleySequence) < 0) {
            // case decreasing
            start = mid;
        } else if (checkSlope(mid, valleySequence) > 0) {            
            // case increasing
            end = mid;
        } else {
            // find our target
            return valleySequence[mid];
        }
    }

    // left over with two points
    if (valleySequence[start] < valleySequence[end]) {
        return valleySequence[start];
    }
    return valleySequence[end];
}

辅助函数checkSlope(index, list) 将检查列表索引处的斜率，它将检查三个点，包括 index - 1、index 和 index + 1。如果斜率是递减，返回负数；如果斜率增加，返回正数；如果index-1和index+1处的数都大于index处的数，则返回0；

注意:该算法假设:

• 列表至少包含三个项目
• 相邻元素处的斜率不可能是平的，这是因为如果有相邻的数是相等的，那么我们就无法判断底在哪边。它可能出现在这种平坦斜坡的左侧或右侧，因此我们将不得不进行线性搜索。

由于数组的随机访问已经是常量 O(1)，拥有 O(logn) 访问时间可能对算法没有帮助。