Share my JAVA solution with detailed explanation, binary search


  • 3
    R

    We use binary search for this question.
    There are 4 scenarios to consider:

    1. mid is at the lowest
    2. mid is at peak
    3. mid is at the increasing slope
    4. mid is at the decreasing slope.

    Use the following algorithm we can achieve O(logn) time complexity and O(1) space complexity.

    public class Solution {
        public int findPeakElement(int[] nums) {
            //corner case
            if (nums.length==0 || nums==null){
                return 0;
            }
            int start=0;
            int end= nums.length-1;
            
            while(start+1<end){
                int mid = start+ (end-start)/2;
                 //peak
                if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]){
                    return mid;
                }
                //decreasing
                else if(nums[mid]<nums[mid-1]){
                    end=mid;
                }
                //increaseing : A[mid] > A[mid - 1]  
                //lowest : A[mid] < A[mid - 1] && A[mid] < A[mid + 1]
                else{
                    start=mid;
                }
                
            }
            if(nums[start]>nums[end]){
                return start;
            }
            else{
                return end;
            }
            
        }
    }

  • 0
    J

    There is no assumption that input is a sorted array. Why binary search can be applied here ?


  • 0
    R

    For this question, the entire input array doesn't need to be sorted for us to use the binary search. only subsets of array need to be sorted - one that lead to the peak and one that after the peak. Think of it as a sign wave.

    According to the question, num[i] ≠ num[i+1], so we know there will be a peek element in this array, as long as array length is not 0.

    Think of it as a sine wave. there will be one or more peak, we just don't know where. our goal is to find it ( any of it)

    So, we started by taking a random point - the mid point of this array.

    1. If that mid point is at the increasing slope, we can eliminate the left part because left part won't contain peak.
    2. if that mid point is at the decreasing slope, we can eliminate the right part since the right part won't contain it.
    3. if the mid point happen to be the peak, we found it.
    4. if that mid point happen to be at the lowest, it doesn't matter which direction we search next.

    Note that we can also use brute force to go through each element, but it will have O(n) time complexity.

    Hope this help. :)


  • 0
    J

    After posting the comment, if it sorted, the peak element should be either the first or the last element of the array.


  • 0
    R

    For this question, the entire input array doesn't need to be sorted for us to use the binary search. only subsets of array need to be sorted - one that lead to the peak and one that after the peak. Think of it as a sign wave.

    For example: [1,2,3,4,3,2,1] - the peak is 4. [1,2,3, 4] is sorted in ascending order. [4, 3,2,1] is sorted in descending order.


  • 0
    R

    if this question is asked for 1st or last peak, then yeah we can't use binary search. will have to use brute force.


  • 0

    Thanks for your share, and I think it's a good one! But the comment for increasing seems confusing.
    //increasing & lowest (A[mid]>A[mid-1]) && (A[mid]<A[mid-1]&& A[mid]>A[mid+1]


  • 1
    P

    @dryear
    I think there is slip of pen here. It should be

    increaseing : A[mid] > A[mid - 1]  
    lowest : A[mid] < A[mid - 1] && A[mid] < A[mid + 1]

  • 0

    @ritakuo statement 1 and 2 is not true

    Take statement 1 for example, we can eliminate the left part just because there must be a peak in the right part, rather than there is no peak in the left part. We don't care whether the left part contains a peak or not.


  • 0
    R

    @pobenliu yes


  • 0
    R

    @LuckyPants i think we are saying the same thing...I


  • 0
    R

    @dryear sorry for the confusion. I've edit the comment


  • 0
    5

    if the array is null or array length is 0, I think you need to return -1 rather than 0. this question is asked to return index.


Log in to reply
 

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