Looking for peak [Abstract dichotomy exercise]

Preface

It's not an examination of dead knowledge points , This kind of problem is very difficult , It's also interesting to push it out slowly . This kind of problem has abstract dichotomy / Greedy algorithm brain teaser .

One 、 Looking for peaks

Two 、 Abstract dichotomy

	public int findPeakElement(int[] nums) {
    
        //  There must be a peak , It indicates that there is no continuous increase , This sum logN What's the connection ？
        int low = 0,high = nums.length - 1;

        while(low < high){
    
            int mid = low + (high - low >>> 1);
            int midVal = nums[mid];
            //  There must be a peak on the right .
            if(midVal < nums[high]) low = mid + 1;
            //  There must be a peak on the left .
            else if(midVal < nums[low])high = mid - 1;
            // nums[low] <= midVal >= nums[high]
            /*  Give Way high--, If high It's the peak , Then there must be comparison nums[high - 1] < nums[high],  and nums[low] <= midVal, be nums[high - 1] There must be a peak before . */
            else --high;

        }
        return low;
    }

summary

1） It's difficult for this / A clever question , Need to understand the description of the topic , Dig inside conditions , Find and have learned the relationship between data structures and algorithms . If you don't settle down to analyze with known conditions , There will be no idea , If not, just look at the solution , Explain that there is less exercise , I can't think of it for months , A waste of time ！
2） There is no fixed formula , Give more examples on the draft paper , Simulation simulation , Find rules and feelings , Then use the data structure to express it , Last review Slowly precipitate a little routine .
3） The most important thing is to do more such topics , Take a look at these excellent solutions , Broaden the following vision , Analysis is more fluent , To draw inferences slowly .

reference

[1] LeetCode Looking for peaks