Simple 8 ms C++ Solution Using Binary Search


  • 5
    C
     class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            int left = 0;
            int right = num.size()-1;
            while(left<right){
                int mid = (right+left)/2;
                if(num[mid]<num[mid+1]){
                    left = mid+1;
                }
                else right = mid;
            }
            return right;
        }
    };
    

    This problem is a binary search,but we should do a litte change.

    the PeakElement is the largest in the neighbor,when our elment is small than the next one it means that the
    peak is in the [mid+1,left],else the peak is in the [right,mid].


  • 0
    H

    How could you let "right" mean "←" ......Or I misunderstood?


  • 0
    S
    This post is deleted!

  • 0
    H

    you should know that the A[-1] and A[A.length] is -MAX_INT, so the answer will be 7 if the input is 1 6 3 5 7 I think


  • 0
    S
    This post is deleted!

  • 0
    C

    You are right , but both 6 and 7 are the pikes according to this problem.
    and return one of them is correct.
    "The array may contain multiple peaks, in that case return the index to any one of the peaks is fine."


  • 0
    C

    Sorry,I finally know what you mean.
    So I have change the code.
    By the way,I cannot figure out left and right....
    T T


  • 1
    A

    I have a little confusion. if our element is small than the next element, it means that the peak should be in the range [mid+1, left], I agree with this part. However, why the element is larger than the next element, the peak should be in range [right, mid] instead of [right,mid-1]

    Of course I knew your code is correct and I did ran through your code with some small edge cases which is easy to have bugs. I am amazed about the delicacy of the else right=mid part. I wonder how you manage to think up that brilliant part.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.