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

GeorgeDeng · 2025-10-09 09:38:36 · 休闲·娱乐

众所周知，在一个数组内部可以通过擂台法求出一个数组的最大值，时间复杂度 O(n)。但是如果我们遇到不要脸的出题人，卡你时间，难道我们就没招了吗？

这时候我们就要审题了：有序数组，这启示我们使用二分查找求出最大值。

于是我们二分查找一个下标 mid，如果 a_{mid}\le a_n，说明还可以往右，否则就往左，时间复杂度 O(\log n)。

下面是实现代码：

#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\sim n 内部三分就行了，时间复杂度 O(\log_3 n)。

#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) 的，因为基本上跑的都是 3ms 时间的。