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