寻找点数组中的最小值的算法

Question

我有一个值向量，它在最小值之后不减，在最小值之前不增。这是一个例子：

std::vector<int> arr = {90, 80, 70, 60, 55, 62, 71, 89, 104}

在这个例子中，我想找到数字55。 我希望能够高效地找到它的最小值。 O(n)时间复杂度不够快。据说可以通过修改二分查找来解决，但我想知道是否存在其他解决方案。

- fiendfire28

---

好的。在此元素之前，它是非递增的，在此元素之后，它是非递减的。 - fiendfire28

如果数组已排序，您可以使用二分查找或斐波那契搜索。然而，对于小数组来说，任何比线性搜索更复杂的算法都不会被忽略。 - Thomas Matthews

我这么说，我明确地说“在它之后是非递减的，在它之前是非递增的”。 - fiendfire28

抱歉，我没有看到那部分。 - Barmak Shemirani

没有内置的功能，但是你对修改后的二分查找足够普遍的情况下是正确的。 - Stephen Newell

@fiendfire28：不幸的是，“它之后不减少，之前不增加”（保证没有局部最小值）并不像凸性那样强，也不足以使二分查找起作用。考虑以下没有局部最小值但不是凸的输入：“3, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3”。将中间元素与其任一邻居进行比较对您毫无意义。 - Ben Voigt

Answer 1

你可以按照以下方式实现O(lg n)的复杂度：

int findTurningPoint(const vector<int>& v, int begin, int end) {
    int mid = (begin + end) / 2;
    if (v[mid - 1] > v[mid] && v[mid + 1] > v[mid]) {
        return mid;
    } else if (v[mid - 1] > v[mid]) {
        return findTurningPoint(v, mid + 1, end);
    } else if (v[mid - 1] < v[mid]) {
        return findTurningPoint(v, begin, mid - 1);
    }
}

vector<int> arr = {90, 80, 70, 60, 55, 62, 71, 89, 104};
cout << findTurningPoint(arr, 0, arr.size() - 1); // 4

方法解释:

选择向量中间的元素。通过与它的邻居进行比较，检查其是否形成极小值。如果没有，则找出该元素及其邻居是否形成递增序列。如果是，则对中间元素左侧的所有元素重复上述过程。否则，重复该过程以对中间元素右侧的所有元素进行操作。

- Wais Kamal

---

如果在幸运地恰好落在最小值的情况下放弃提前退出，则每个步骤只需进行两次比较（begin < end和 v[mid] < v[mid+1]）。您当前的实现可能会读取数组的两端，这也是一个问题。 - Ben Voigt

如果您放弃在获取到最小值的幸运情况下提前退出，那么每个步骤只需要两次比较（begin < end 和 v[mid] < v[mid+1]），这样可以实现递归。但是如果消除了“幸运情况”，则递归将永远不会停止。 - Wais Kamal

抱歉，我的错。同时这个 mid = (begin - end) / 2。 - Wais Kamal

我的建议是，如果每次迭代/递归的成本可以大幅降低，那么最好让搜索运行直到begin>=end（更多迭代）。现在，每次迭代/递归最多有6个比较，而且你仍然没有处理基本情况（因为begin==end可能从第一个调用就为真），所以至少有7个比较。将其减少到2或3可能是一种净胜利，即使没有早期退出，平均迭代/递归计数也会增加。 - Ben Voigt

@WaisKamal 供以后参考，在二分查找中提前退出只能平均节省一次循环。例如，想象一下对包含127个元素的数组进行二分查找。只有1个元素在第一次尝试中被找到。127个元素中的2个将在第二次尝试中找到。3次尝试中找到4个，4次尝试中找到8个，5次尝试中找到16个，6次尝试中找到32个，7次尝试中找到64个。平均尝试次数略高于6次。因此，平均而言，提前退出可以节省一次循环。 - user3386109