C ++で最初に増加し、次に減少する配列内の最大要素を見つけます

最初に増加してから減少する配列が1つあるとします。配列内の最大値を見つける必要があります。したがって、配列要素がA =[8、10、20、80、100、250、450、100、3、2、1]のような場合、出力は500になります。

これを解決するために二分探索を使用することができます。 3つの条件があります-

• midが隣接する両方の要素よりも大きい場合、midが最大になります
• midが次の要素よりも大きいが、前の要素よりも小さい場合、maxはmidの左側にあります。
• mid要素が次の要素よりも小さいが、前の要素よりも大きい場合、maxはmidの右側にあります。

例

#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
   if (left == right)
      return array[left];
   if ((right == left + 1) && array[left] >= array[right])
      return array[left];
   if ((right == left + 1) && array[left] < array[right])
      return array[right];
   int mid = (left + right)/2;
   if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
      return array[mid];
   if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
      return getMaxElement(array, left, mid-1);
   else
      return getMaxElement(array, mid + 1, right);
}
int main() {
   int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
   int n = sizeof(array)/sizeof(array[0]);
   cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
}

出力

The maximum element is: 450