学习工控知识，就来工控小新

农历十一月二十五日 2024/1/ 6

往期推荐

2024年1月4日，每日花费一分钟练习C语言

2024年1月5日，每日花费一分钟练习C语言

每日一练

/ Daily Exercises

题目：

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素

给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰

值所在位置即可。

你可以假设nums[-1] = nums[n] = -

你必须实现时间复杂度为 0(log n)的算法来解决此问题。

题目分析

为了实现一个对数时间的算法，我们可以考虑使用二分查找的思想。二分查找是一种在有序数组中查找目标值的算法，它的基本思想是，每次比较数组的中间元素和目标值，如果相等则返回，如果不等则根据大小关系，舍弃一半的数组，继续在剩下的一半数组中查找，直到找到目标值或数组为空。

我们可以将这个思想应用到寻找峰值元素的问题上，但是有一些不同之处。首先，我们不是在有序数组中查找目标值，而是在无序数组中查找峰值元素。其次，我们不是比较数组的中间元素和目标值，而是比较数组的中间元素和其左右相邻元素。最后，我们不是根据大小关系，舍弃一半的数组，而是根据峰值的定义，舍弃一侧的数组，继续在另一侧的数组中查找。

具体来说，我们可以定义一个函数findPeak，它接受一个数组nums和两个整数left和right，表示要查找的数组的左右边界。我们可以假设left和right都是有效的索引，且left <= right。函数的返回值是一个峰值元素的索引，如果不存在则返回-1。

程序展示

如果left > right，说明数组为空，没有峰值元素，返回-1。

- 如果left == right，说明数组只有一个元素，它就是峰值元素，返回left。

- 否则，计算数组的中间索引mid = (left + right) / 2，比较nums[mid]和nums[mid + 1]的大小关系。

- 如果nums[mid] > nums[mid + 1]，说明mid处于一个下降的区间，那么峰值元素可能在mid的左侧，或者就是mid本身，所以我们可以在[left, mid]的区间中继续查找，即返回findPeak(nums, left, mid)的结果。

- 如果nums[mid] < nums[mid + 1]，说明mid处于一个上升的区间，那么峰值元素可能在mid的右侧，所以我们可以在[mid + 1, right]的区间中继续查找，即返回findPeak(nums, mid + 1, right)的结果。

- 如果nums[mid] == nums[mid + 1]，说明mid处于一个平坦的区间，那么峰值元素可能在mid的两侧，或者不存在，所以我们可以在任意一侧的区间中继续查找，比如返回findPeak(nums, left, mid)的结果。

这个算法的时间复杂度是O(log n)，因为每次我们都会舍弃一半的数组，所以最多需要进行log n次查找。空间复杂度是O(log n)，因为我们使用了递归，所以需要额外的栈空间来存储递归调用的信息。

#include<stdio.h>// 寻找峰值元素的函数，接受一个数组nums，一个数组的长度n，和两个整数left和right，表示要查找的数组的左右边界// 返回一个峰值元素的索引，如果不存在则返回-1int findPeak(int nums[], int n, int left, int right) {    // 如果left > right，说明数组为空，没有峰值元素，返回-1    if (left > right)   {        return -1;    }    // 如果left == right，说明数组只有一个元素，它就是峰值元素，返回left    if (left == right)   {        return left;    }    // 否则，计算数组的中间索引mid    int mid = (left + right) / 2;    // 比较nums[mid]和nums[mid + 1]的大小关系    if (nums[mid] > nums[mid + 1])   {        // 如果nums[mid] > nums[mid + 1]，说明mid处于一个下降的区间，那么峰值元素可能在mid的左侧，或者就是mid本身        // 所以我们可以在[left, mid]的区间中继续查找，即返回findPeak(nums, n, left, mid)的结果        return findPeak(nums, n, left, mid);    }  else if (nums[mid] < nums[mid + 1])   {        // 如果nums[mid] < nums[mid + 1]，说明mid处于一个上升的区间，那么峰值元素可能在mid的右侧        // 所以我们可以在[mid + 1, right]的区间中继续查找，即返回findPeak(nums, n, mid + 1, right)的结果        return findPeak(nums, n, mid + 1, right);    }   else  {        // 如果nums[mid] == nums[mid + 1]，说明mid处于一个平坦的区间，那么峰值元素可能在mid的两侧，或者不存在        // 所以我们可以在任意一侧的区间中继续查找，比如返回findPeak(nums, n, left, mid)的结果        return findPeak(nums, n, left, mid);    }}// 主函数，测试findPeak函数的功能int main() {    // 定义一个测试用的数组nums    int nums[] = {1, 2, 1, 3, 5, 7, 4};    // 获取数组的长度n    int n = sizeof(nums) / sizeof(nums[0]);    // 调用findPeak函数，传入数组nums，数组的长度n，和数组的左右边界0和n - 1    // 将返回值赋给变量peak    // 调用findPeak函数，传入数组nums，数组的长度n，和数组的左右边界0和n - 1    // 将返回值赋给变量peak    int peak = findPeak(nums, n, 0, n - 1);    // 如果peak不等于-1，说明找到了峰值元素，打印其索引和值    if (peak != -1)   {        printf("The peak element is at index %d, and its value is %d.\n", peak, nums[peak]);    }   else   {        // 如果peak等于-1，说明没有找到峰值元素，打印提示信息        printf("There is no peak element in the array.\n");    }    // 返回0，表示程序正常结束    return 0;}

程序测试

为了验证我们的程序是否正确，我们可以用一些测试用例来检验。

这就是我用C语言写的寻找峰值元素的程序，它可以在VC6.0的环境下运行。你可以尝试用不同的数组来测试它的功能，看看它是否能正确地找到峰值元素。

源代码获取

#软件下载通道#

我用夸克网盘分享了「20240106」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。

链接：

(链接和提取码建议复制粘贴，手动输入容易出现错误）

#支持一下#

分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓

谢谢大家！

下期题目

C语言题目：二进制求和，给你两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字1和0

点赞加关注，学习不迷路

微信公众号｜工控小新

EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中

#头条挑创作挑战赛#

#学习C语言#