C++二分算法的应用：寻找峰值原理、源码及测试用例

说明

此文是课程https://edu.csdn.net/course/detail/38771 的讲义。

源码下载：https://download.csdn.net/download/he_zhidan/88458478

本文涉及的基础知识点

二分查找算法合集

题目

长度为n的数组nums，请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。

题目保证nums[i]不等于nums[i+1]。

2023年11月14整补

有读者反应看不懂，感谢他的建议，特增补如下。

定义

原始数组的连续区域称为子数组。如果一个子数组的首元素在原始数组的索引为i，尾元素在原始数组的索引为j，则用nums[i,j]表示此子数组，也可以用nums[i,j+1)表示。如果nums[i,j]同时符合以下两个条件，则是好子数组。

一，i为0或nums[i]>nums[i-1]。

二，j为n-1或nums[j]>nums[j+1]

推论

一，如果好子数组nums[i,j]的长度为1，则i就是峰值。

二，如果好子数组nums[i,j]的长度大于1，则从nums[i,j]找出一个比nums[i,j]短的好子数组nums[i1，j1]。

三，由于长度不断变短，长度一定会变为1。

举例

1 2

1 2 =>2 (1不是好子数组 2是，长度降为1结束)

2 1

2  1 =>2 (2是好子数组 ，1不是,长度降为1结束)

1 2 3

1 2 3 => 2 3(1不是好子数组，2 3是)=> 3(3是好数组长度降为1结束)

3 2 1

1 2 3 => 3

1 3 2

1 3 2 => 3 2 => 3

1到4

1 2 3 4 => 3 4 => 4

1 2 4 3 => 4 3 => 4

1 3 2 4=> 1 3 => 3

1 3 4 2 => 4 2 => 4

1 4 2 3=> 1 4=> 4

1 4 3 2=> 1 4=> 4

...

2 4 1 3 => 2 4 => 4

其它

1 2 3 4 5 6 7 8 => 5 6 7 8 => 7 8 => 8

9 8 7 6 5 4 3 2 1 => 9 8 7 6 => 9 8 = > 9

1 3 5 7 9 8 6 4 2 => 9 8 6 4 2 = > 9 8 => 9

总结

将好子数组nums[i,j] 分成左右两个子数组nums[i,mid)和nums[mid,j]

如果nums[mid]> nums[mid-1] 则nums[mid,j]是好子数组

否则 nums[i,mid)是好子数组

分析

假定：

nums[left,r)符合nums[left]>nums[left-1]，且nums[r-1]>nums[r]。显然初始情况nums[0,n)符合。

推论一：如果[left,r)的长度为1，则left就是返回的索引。

推论二：假定left < mid<r。如果mid[mid] > mid[mid-1],则nums[mid,r)也符合假定。如果mid[mid] < mid[mid-1]，则nums[left,mid)也符合假定。

推论三：推论二也可以也可以理解成分别抛弃[left,mid)和[mid,r)。令mid = left+(r-left)/2，由于r-left>=2，所以left<mid<r。也就是抛弃的子数组不会为空。也就是数组不断变短。等长度为1结束。

时间复杂度

由于每次抛弃一半，所以需要抛弃logn次。故时间复杂度O(logn)

核心代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, r = nums.size();
        while (r - left > 1)
        {
            const int mid = left + (r - left) / 2;
            if (nums[mid] > nums[mid - 1])
            {
                left = mid;
            }
            else
            {
                r = mid;
            }
        }
        return left;
    }
};

测试用例

int main()
{
    Solution slu;
    vector<int> nums = { 1,2,3,4 };
    int res = slu.findPeakElement(nums);
    assert(3 == res);
    nums = { 4,3,2,1 };
    res = slu.findPeakElement(nums);
    assert(0 == res);
    nums = { 2,5,3,1 };
     res = slu.findPeakElement(nums);
    assert(1 == res);
}

其它

学院课程

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

每天都补充正能量

相关下载

如果你时间宝贵，只想看精华，请到CSDN下载频道下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653