在点数组中找到最小值的算法

Question

我有一个具有最小值的向量，但在它之后不减少，之前不增加。这是示例：

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

在例子中我想找到55。我希望能够有效地找到它的最小值。 O(n) 复杂度是不够的。据说可以修改二分查找，但是我想知道是否有现成的解决方案。

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

方法解释：

Select 向量中间的元素。通过与邻居比较来检查它是否形成最小值。如果不是，则查找该元素及其邻居是否构成递增序列。如果是，则对中间元素左侧的所有元素重复上述过程。否则，对中间元素右侧的所有元素重复该过程。

在点数组中找到最小值的算法

Algorithm to find minimum in array of point

c++

algorithm

search