c++ - 在点数组中找到最小值的算法
问题描述
我有一个具有最小值的值向量,但在它之后不减少,之前不增加。这是示例:
std::vector<int> arr = {90, 80, 70, 60, 55, 62, 71, 89, 104}
在示例中,我想找到 55。我希望能够有效地找到它的最小值。O(n) 复杂度是不够的。据说,可以对二进制搜索进行某种修改,但我想知道是否有现有的解决方案。
解决方案
您可以实现 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
方法说明:
选择向量中间的元素。通过与邻居比较来检查它是否形成最小值。如果不是,则查找该元素及其相邻元素是否形成递增序列。如果是这样,请对中间元素左侧的所有元素重复上述过程。否则,对中间元素右侧的所有元素重复该过程。
推荐阅读
- javascript - 关于使用 JQuery 从文本 API 加载评论的问题
- apache - 如何在 htaccess 中获得这个 if-else 重定向?
- powershell - 包含重复项的数组
- html - 为什么向左/向右浮动不起作用?试图将照片和文字对齐
- angularjs - 使用 AngularJS 在 HTML 中连接
- rxjs - 如何将第三方事件绑定到 rxjs observable
- android - 如何让导航抽屉中的项目自动一一点击?
- python - 错误 Python:TypeError List() 不可调用
- python - Django 注册视图:TypeError: 'set' object is not subscriptable
- python - 如何仅从 HTML 代码中打印和求和数字?(Python)