資料結構
網路技術
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 檢視
廣告