在C ++中的数组中找到局部最小值

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个包含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

以上是 在C ++中的数组中找到局部最小值 的全部内容， 来源链接： utcz.com/z/354285.html

回到顶部