使用二进制搜索方法查找数组峰值元素的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
热门推荐
1 训练狗狗基础
2 怎么训练狗狗笑
3 怎么训练狗狗卧下
4 上海狗狗训练基地
5 训练狗狗排便
6 狗狗基础训练
8 如何训练狗狗装死
9 狗狗站姿训练
10 狗狗训练用品
11 训练狗狗吧
12 狗狗要怎么训练
13 怎么训练狗狗玩球
14 训练狗狗唤回
15 狗狗训练躺下
16 狗狗训练指令
17 狗狗的训练技巧
18 狗狗不好训练