数据结构
网络技术
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用二分查找法查找数组峰值的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
更新日期: 30-Jul-2019
820 查看
广告