数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 C++ 中找出数组中的局部最小值
假设我们有一个包含 n 个元素的数组 A。我们需要找到数组的局部最小值。在数组 A 中，元素 A[x] 被认为是局部最小值，如果它小于或等于其两个相邻元素。对于角元素，只考虑一个相邻元素。如果有多个局部最小值，则只返回一个。例如，如果数组类似于 [9, 6, 3, 14, 5, 7, 4]，则局部最小值可以为 3、5 和 4，因此此算法只能返回其中一个。
为了解决这个问题，我们将遵循二分搜索之类的逻辑。如果中间元素小于其左侧和右侧元素，则返回 mid，否则，如果大于了左侧相邻元素，则在左侧可能存在一些局部最小值，如果大于了右侧元素，则在右侧将存在一些局部最小值，对它们执行相同的任务以找到精确的局部最小值。
示例
#include<iostream>
using namespace std;
int localMinima(int arr[], int left, int right, int n) {
int mid = left + (right - left)/2;
if ((mid == 0 || arr[mid-1] > arr[mid]) && (mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinima(arr, left, (mid -1), n);
return localMinima(arr, (mid + 1), right, n);
}
int findLocalMinima(int arr[], int n) {
return localMinima(arr, 0, n-1, n);
}
int main() {
int arr[] = {9, 6, 3, 14, 5, 7, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Local minima is: " << arr[findLocalMinima(arr, n)];
}输出
Local minima is: 3
更新于： 2019-12-18
374 次浏览
广告