专栏文章

全新的在有序数组中求最大值的方法

GGeorgeDeng
休闲·娱乐参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minnfnlp
此快照首次捕获于
2025/12/02 05:16
3 个月前
此快照最后确认于
2025/12/02 05:16
3 个月前
查看原文
众所周知，在一个数组内部可以通过擂台法求出一个数组的最大值，时间复杂度 O(n)O(n)。但是如果我们遇到不要脸的出题人，卡你时间，难道我们就没招了吗？
这时候我们就要审题了：有序数组，这启示我们使用二分查找求出最大值。
于是我们二分查找一个下标 midmid，如果 amid≤ana_{mid}\le a_n，说明还可以往右，否则就往左，时间复杂度 O(log⁡n)O(\log n)。
下面是实现代码：
CPP
#include <iostream>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;

int n;
vector<int> a;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++){
        int x;
        cin>>x;
        a.push_back(x);
    }
    int l = 0,r = a.size()-1;
    int ans = 0;
    while(l<=r){
        int mid = (l+r)>>1;
        if(a[mid]<=a[a.size()-1]){
            ans = mid;
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    cout<<"Maximum number index (Index from 0): "<<ans<<endl;
    cout<<"Maximum number: "<<a[ans];
    return 0;
}
什么你说上面那种写法太假了？我们还可以编出一个三分写法：
我们可以看做原数组为一个上升的一段，后面直线下降，单峰函数求最大值可以使用三分，但是只需要在 1∼n1\sim n 内部三分就行了，时间复杂度 O(log⁡3n)O(\log_3 n)。
CPP
#include <iostream>
#include <vector>
#define int long long
#define endl '\n'
using namespace std;

int n;
vector<int> a;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++){
        int x;
        cin>>x;
        a.push_back(x);
    }
    int l = 0,r = a.size()-1;
    int ans = 0;
    while(l<=r){
        int mid1 = l+(r-l)/3;
        int mid2 = r-(r-l)/3;
        if(a[mid1]<=a[mid2]){
            ans = mid1;
            l = mid1+1;
        }else{
            r = mid2-1;
        }
    }
    cout<<"Maximum number index (Index from 0): "<<ans<<endl;
    cout<<"Maximum number: "<<a[ans];
    return 0;
}
出题人一般卡不掉 O(log⁡n)O(\log n) 的，因为基本上跑的都是 3ms3ms 时间的。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...