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

序列 A=[a1, a2,...,an] 是一个谷序列，如果有一个索引 i 且 1 a1 > a2 > .... > ai和ai < ai+1 < .... < an.给定一个谷序列必须至少包含三个元素。我真正感到困惑的是，我们如何找到一个算法，如上所述，在 O(log n) 时间内找到元素 ai？它会类似于 O(log n) 二分查找吗？如果我们确实有一个二进制搜索算法可以在 O(log n) 时间内找到数组的元素，我们能否将运行时间提高到 O(log log n) ？ 最佳答案 要使用 BIG-O(logn) 算法，我们必须在恒定时间内将问题大小减少一半。具体在这个问题中，我们可以选择一个中点，并检查它的斜率是增加、减少还是底部。 如果斜率增加，中点之后的部分可以忽略 否则，如果斜率在减小，则可以忽略中点之前的部分 否则中点应该是底部，因此我们找到了目标。 Java代码示例:输入:[99, 97, 89, 1, 2, 4, 6]，输出:1public 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) 访问时间可能对算法没有帮助。关于在序列中找到元素 ai 的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46780250/