使用二进制搜索方法查找数组峰值元素的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
热门推荐
10 有新年红包祝福语简短
11 可爱伴娘祝福语高级简短
12 照顾自己生日祝福语简短
13 妈妈求婚祝福语大全简短
14 妈妈生日简短祝福语儿子
15 乔迁大吉花束祝福语简短
16 兄弟生日祝福语日语简短
17 爸爸生日祝福语简短干净
18 生日祝福语致外婆简短