162. Find Peak Element

162. Find Peak Element

寻找峰顶元素的下标 简单画一个图,可以发现山峰元素和它的下一个元素的关系 O(N)

int findPeakElement(const vector<int> &num) {
    for(int i = 1; i < num.size(); i ++)
    {
        if(num[i] < num[i-1])
        {// <
            return i-1;
        }
    }
    return num.size()-1;
}

O(logN) 典型的二分查找

int findPeakElement(const vector<int> &num) {
    int low = 0;
    int high = num.size()-1;
        
    while(low < high)
    {
        int mid1 = (low+high)/2;
        int mid2 = mid1+1;
        if(num[mid1] < num[mid2])
            low = mid2;
        else
            high = mid1;
    }
    return low;
}

#二分 #array