在C ++中找到先增加然后减少的数组中的最大元素
假设我们有一个数组,它最初是增加然后减少。我们必须在数组中找到最大值。因此,如果数组元素类似于A=[8、10、20、80、100、250、450、100、3、2、1],则输出将为500。
我们可以使用二进制搜索来解决这个问题。有三个条件-
当mid大于两个相邻元素时,mid是最大值
如果mid大于下一个元素,但小于上一个元素,则max位于mid的左侧。
如果mid元素小于下一个元素,但大于前一个元素,则max位于mid的右侧。
示例
#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
if (left == right)
return array[left];
if ((right == left + 1) && array[left] >= array[right])
return array[left];
if ((right == left + 1) && array[left] < array[right])
return array[right];
int mid = (left + right)/2;
if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
return array[mid];
if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
return getMaxElement(array, left, mid-1);
else
return getMaxElement(array, mid + 1, right);
}
int main() {
int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
int n = sizeof(array)/sizeof(array[0]);
cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
}输出结果
The maximum element is: 450
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下