My logn answer in C++


  • 5
    C
    class Solution {
    public:
        int findPeakElement(vector<int>& nums) 
        {
            if(nums.size() <= 1)
                return 0;
            return peakIndex(nums, 0, nums.size() - 1);
        }
        
        int peakIndex(vector<int>& nums, int begin, int end)
        {
            if(begin > end)
                return -1;
            int mid = (begin + end) / 2;
            int left = (mid - 1) < 0 ? INT_MIN : nums[mid - 1];
            int right = (mid + 1) > (nums.size() - 1) ? INT_MIN : nums[mid + 1];
            
            if(nums[mid] > right && nums[mid] > left)
                return mid;
            if(mid > 0 && nums[mid - 1] > nums[mid])
                return peakIndex(nums, begin, mid - 1);
            else
                return peakIndex(nums, mid + 1, end);
        }
    };

  • 0
    Y

    Will it work? For [5, 4, 3, 2, 6, 4]. nums[mid - 1] > nums[mid] and it will search the smaller half and will not find the peak.


  • 0
    C

    If it searches the smaller half then the peak will be 5. Note that the problem wants you to find any peak.


  • 0
    Y

    Thanks! I just missed num[-1] = num[n] = -∞


Log in to reply
 

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