数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学在 C++ 中查找先递增后递减数组中的最大元素
假设我们有一个数组，它先递增后递减。我们必须找到数组中的最大值。所以如果数组元素类似 A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1]，则输出将为 450。
我们可以使用二分查找来解决这个问题。有三种情况：
- 当中间元素大于其两个相邻元素时，则中间元素为最大值。
- 如果中间元素大于下一个元素，但小于前一个元素，则最大值位于中间元素的左侧。
- 如果中间元素小于下一个元素，但大于前一个元素，则最大值位于中间元素的右侧。
示例
#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
更新于：2019年12月17日
245 次浏览
广告