C 语言查找数组中先递增后递减的最大元素

在本文中，我们将讨论如何在 C 语言中找到一个先递增然后递减的数组中的最大元素。以下是一些关于数字数组中最高值的示例，这些数组最初是递增然后递减的。

示例

示例 1

输入： arr[] = {5, 10, 15, 12, 8, 3}

输出 15

此示例显示了一个数组，该数组最初从 5 增加到 15，然后下降，最大值为 15。

示例 2

输入： arr[] = {2, 4, 6, 10, 8, 5, 3}

输出 10

在此示例中，一个数组最初从 2 增加到 10，然后下降，最大值为 10。

示例 3

输入： arr[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}

输出 5

在这里，我们将采用几种方法来解决这个问题。这些方法如下：

方法 1：线性搜索

在此方法中，可以遍历数组，同时跟踪最大和元素。之后，它返回最大的元素。

程序

输出

The maximum element is 89

方法 2：使用二分查找 - 递归解决方案

在此方法中，我们使用二分查找迭代地找到一个先递增然后递减的数组中的最大成员。

以下是一些可以修改传统二分查找方法的方式：

• 如果中间元素大于其相邻元素，则中间元素是最大的。
• 如果中间元素小于其后续元素，我们应该尝试在数组的右半部分进行搜索。决定 low = mid + 1。数组示例：2, 4, 6, 8, 10, 3,
• 与此类似，如果中间元素大于后续元素，我们应该尝试在左侧进行搜索。决定 high = mid - 1。数组示例：3, 50, 10, 9, 7, 6。

程序

输出

The maximum element is 50

说明

在此示例中，findMaximum 函数使用递归二分查找来识别数组中的最大条目。之后，main 函数打印出最大元素，即 50。

方法 3：使用二分查找迭代地查找先递增然后递减的数组中的最大成员。

以下是可能对典型二分查找方法进行的更改：

• 如果中间元素大于其相邻元素，则中间元素是最大的。
• 如果中间元素小于其后续元素，我们应该尝试在数组的右半部分进行搜索。因此，将 low = mid + 1。数组示例：2, 4, 6, 8, 10, 3，
• 与此类似，如果中间元素大于后续元素，我们应该尝试在左侧进行搜索。决定 high = mid - 1。数组示例：3, 50, 10, 9, 7, 6。

C++ 程序

输出

The maximum element is 60

说明

在此示例中，maxInBitonic 函数使用迭代二分查找方法查找双调数组中的最大条目。之后，main 函数打印出最大元素，即 60。

方法 4：堆栈

1. 在此方法中，创建一个空堆栈来存储数组元素的索引。
2. 从左到右遍历数组，直到找到最多的元素。只要元素小于或等于其前面的元素，就将每个元素的索引压入堆栈。
3. 当发现一个元素大于其前面的元素时，我们就知道找到了最大元素。之后，我们可以从堆栈中弹出所有索引，直到找到一个索引，其对应元素大于当前元素。
4. 最大元素是与堆栈的最后一个索引相对应的元素。

C++ 程序

输出

The maximum element is 20