题解 | #寻找峰值#

随机二分搜索

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        // write code here
        if (nums.size() == 1||nums[0]>nums[1]) return 0;
        if (nums[nums.size()-1]>nums[nums.size()-2]) return nums.size()-1;
        return finds(nums, 1, nums.size()-2);
    }
    int finds(vector<int>& arr, int l, int r){
        if (l>r) return -1;
        int mid = (l+r)>>1;
        if (arr[mid-1]<arr[mid] && arr[mid+1]<arr[mid])
            return mid;
        if (rand()%2 == 0){
            int lq = finds(arr, l, mid-1);
            if (lq>=0) return lq;
            int rq = finds(arr, mid+1, r);
            if (rq>=0) return rq;
        }
        else{
            int rq = finds(arr, mid+1, r);
            if (rq>=0) return rq;
            int lq = finds(arr, l, mid-1);
            if (lq>=0) return lq;
        }
        return -1;
    }
};