Tìm một cực tiểu cục bộ trong một mảng trong C ++

Giả sử chúng ta có một mảng A với n phần tử. Chúng ta phải tìm cực tiểu cục bộ của mảng. Trong mảng A, phần tử A [x] được cho là cực tiểu cục bộ nếu nó nhỏ hơn hoặc bằng cả hai phần tử lân cận của nó. Đối với các phần tử góc, chỉ một hàng xóm sẽ được xem xét. Và nếu có nhiều hơn một cực tiểu cục bộ khả dụng, thì chỉ trả về một. Ví dụ:nếu mảng giống như [9, 6, 3, 14, 5, 7, 4], thì cực tiểu cục bộ có thể là 3, 5 và 4, vì vậy thuật toán này chỉ có thể trả về một trong số chúng.

Để giải quyết vấn đề này, chúng ta sẽ tuân theo logic giống như tìm kiếm nhị phân. Nếu phần tử ở giữa nhỏ hơn phần tử bên trái và bên phải của nó, thì trả về giá trị giữa, ngược lại, nếu nó lớn hơn hàng xóm bên trái, thì có thể có một số cực tiểu cục bộ ở phía bên trái, nếu nó lớn hơn phần tử bên phải thì ở đó sẽ là một số cực tiểu cục bộ ở bên phải, hãy làm nhiệm vụ tương tự để chúng tìm ra cực tiểu cục bộ chính xác.

Ví dụ

#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)];
}

Đầu ra

Local minima is: 3