C++에서 처음 증가하고 감소하는 배열의 최대 요소 찾기

처음에는 증가하다가 감소하는 배열이 하나 있다고 가정합니다. 배열에서 최대값을 찾아야 합니다. 따라서 배열 요소가 A =[8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1]과 같으면 출력은 500이 됩니다.

이진 검색을 사용하여 이 문제를 해결할 수 있습니다. 세 가지 조건이 있습니다 -

• mid가 인접한 두 요소보다 크면 mid가 최대값입니다.
• mid가 다음 요소보다 크지만 이전 요소보다 작은 경우 max는 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