이진 검색 접근 방식을 사용하여 배열의 피크 요소를 찾는 C++ 프로그램

이 C++ 프로그램에서 배열의 피크 중 하나를 이진 검색 방식을 사용하여 찾을 수 있음을 찾습니다. 이 알고리즘은 알고리즘의 시간 복잡도가 O(log(n))인 결과로 발견된 첫 번째 피크를 반환합니다.

알고리즘

Begin
   PeakElement() function has ‘arr’ the array of data, start and end index in the argument list.
   Assign the mid of subpart of the array.
   If mid is at the boundary index and value at mid is higher than its neighbor then return mid as peak.
   If the value at mid is greater than both of its neighbors then return mid as peak.
   If the value at the right of mid is greater than mid then send second sub-part of the array into PeakElement() as argument.
   If the value at the left of mid is greater than mid then send first sub-part of the array into PeakElement() as argument.
End

예시 코드

#include<iostream>
using namespace std;
int PeakElement(int a[], int start, int end) {
   int i, mid;
   mid = (end+start+1)/2;
   if((a[mid] > a[mid+1] && mid == start)||(a[mid] > a[mid-1] && mid == end)) {
      return a[mid];
   } else if(a[mid] < a[mid-1] && a[mid] > a[mid+1]) {
      return a[mid];
   } else if(a[mid] <= a[mid+1]) {
      return PeakElement(a, mid+1, end);
   } else if(a[mid] <= a[mid-1]) {
      return PeakElement(a, start,mid-1);
   }
}
int main() {
   int n, i, p;
   cout<<"\nEnter the number of data element: ";
   cin>>n;
   int arr[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   p = PeakElement(arr, 0, n-1);
   cout<<"\nThe peak element of the given array is: "<<p;
   return 0;
}

출력

Enter the number of data element: 5
Enter element 1: 45
Enter element 2: 26
Enter element 3: 70
Enter element 4: 60
Enter element 5: 15
The peak element of the given array is: 70