O(log(N)) complexity C++ solution without recoursion


  • 0
    A
    class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            int size= num.size();
            if(size) {
                if(size==1 || num[0]>num[1])
                    return 0;
                if(num[size-1]>num[size-2])
                    return size-1;
                int left= 0, right= size;
                while(left<right-1) {
                    int m= left+(right-left)/2;
                    bool fwd;
                    if((fwd= num[m-1]<num[m]) && num[m]>num[m+1])
                        return m;
                    if(fwd)
                        left= m;
                    else
                        right= m;
                }
            }
            return -1;
        }
    };

  • 2
    J

    it not a sorted array.
    does binary search work for this problem?
    i doubted that


  • 0
    R

    lot of people using binary search and thinking their order is O(logn).. which is quite stupid as the array isn't sorted.
    However doing binary search will not give wrong result as any peak would yield right answer but a simple O(n) solution is exactly the same as binary search here..


  • 0
    J

    It can, since "You may imagine that num[-1] = num[n] = -∞." and "num[i] ≠ num[i+1]" ensure there is at least a peak. You can draw a parabola and why it works.


  • 0
    M

    why does the array need to be sorted to work? If it was sorted the peak would just be the last element.


  • 0
    J

    u r right. i realized that


  • 0
    D

    This question is really not well designed. Binary search only works with this very vague and artificial constraint "The You may imagine that num[-1] = num[n] = -∞ ". But of course, without this, the question is meaningless.


Log in to reply
 

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