Find the maximum by binary search (recursion and iteration)


  • 217
    G

    Consider that each local maximum is one valid peak.
    My solution is to find one local maximum with binary search.
    Binary search satisfies the O(logn) computational complexity.

    Binary Search: recursion

    class Solution {
    public:
    
    int findPeakElement(const vector<int> &num) {
        return Helper(num, 0, num.size()-1);
    }
    int Helper(const vector<int> &num, int low, int high)
    {
        if(low == high)
            return low;
        else
        {
            int mid1 = (low+high)/2;
            int mid2 = mid1+1;
            if(num[mid1] > num[mid2])
                return Helper(num, low, mid1);
            else
                return Helper(num, mid2, high);
        }
    }
    };
    

    Binary Search: iteration

    class Solution {
    public:
        int findPeakElement(const vector<int> &num) 
        {
            int low = 0;
            int high = num.size()-1;
            
            while(low < high)
            {
                int mid1 = (low+high)/2;
                int mid2 = mid1+1;
                if(num[mid1] < num[mid2])
                    low = mid2;
                else
                    high = mid1;
            }
            return low;
        }
    };
    

    Sequential Search:

    class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            for(int i = 1; i < num.size(); i ++)
            {
                if(num[i] < num[i-1])
                {// <
                    return i-1;
                }
            }
            return num.size()-1;
        }
    };

  • 4
    P

    That sequential search is really wise!


  • -2
    S

    Is that right? correct me if I'm wrong, but what about the case [2,4,1,3,6]?


  • 0
    S

    in your case, 6 is the peak, its left is 3, its right is -oo


  • 0
    F

    can this algorithm find absolute maximum? what if the array is [9, 4, 6, 8, 1, 7]? It seems the index found is 5 which is element 7 though this is qualified as peak element.


  • 0
    F
    This post is deleted!

  • 0
    G

    Thank you for your attention. In fact, every local maximum is one valid peak. Thus I said in the first sentence "Consider that the sequence has only one peak."


  • 0
    F

    Ah, I see. Thanks.


  • 0
    G
    This post is deleted!

  • 0
    W

    Very brilliant, but I don't think saying "Consider that the sequence has only one peak. The problem equals to finding the maximum. " is necessary, because for your solution, it's actually finding the peak instead of finding the maximum, and it happens to be the maximum number because there is only one peak.


  • 0
    A

    The sequential search is really smart!


  • 0
    G

    Yes, you're right. My solution is to find one local maximum, which is a valid peak.


  • 2
    C

    The sequential search seems neat. But it is O(n) not O(logn), isn't it?


  • 0
    G

    Yes, you're right. I proposed it here just for comparison :)


  • 0
    Z
    This post is deleted!

  • 0
    Z

    How about [1,2,1] in Binary Search: iteration? The code didn't get accepted. I added a condition: if (num[mid1] > num[mid2] and num[mid1]>num[mid-1]) return mid; and then it works. Thanks!


  • 0
    I

    Thanks, I learned a lot! The Sequential Search is really great!


  • 0
    O
    This post is deleted!

  • 0
    S

    How about this input:[ 1 2 3 3 2 1] ?


  • 2
    J

    the description of the question said:
    Given an input array where num[i] ≠ num[i+1]

    So there is no double 3 in the array.


Log in to reply
 

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