My binary search java solution


  • 4
    X
    public class Solution {
        public int findPeakElement(int[] num) {
            
            int length = num.length;
            int left = 0;
            int right = length-1;
    
            int a=0;
            while(left<=right){   //左右开工找peak,直到两个element重合为止
                if(left==right){
                   a = left;
                   break;
                } 
                int mid = (left+right)/2;
                
                if(num[mid]<num[mid+1]){
                    left = mid+1;
                }else{
                    right = mid;
                }
                
            }
            return a;
        }
    }

  • 0
    J

    I am curious how this solution works with array {1, 2, 3, 4, 5, 9, 7} ?


  • 0
    J

    this solution does indeed work for the array you provided


  • 0
    J

    Sorry. I think I gave a wrong example. Let's see

    {5, 4, 3, 2, 1, 9, 7}. In your solution, The first mid will be 2. Since it is bigger than 1, we will only look left side after then. And obviously, there is no peak number on left side.

    So, as long as we build a descend order number on left side and make it pass middle point. and make a 
    peak number somewhere on right side. This solution will fail.

  • 0
    G

    So if we want to do it with binary search, it's possible that a peek actually exists but not found.


  • 0
    J

    according to the test cases, if you are on the edge of the array, and the adjacent number is less than you, then you are a peak.

    e.g.
    [1] -> index 0 is the peak a.k.a. 1
    [1, 2] -> index 1 is the peak a.k.a. 2


  • 0
    S

    What about this case : 1, 1, 1, 1, 1, 2 ? I think it will return 1 but correct answer is 2. Since it can contain duplicate number.


  • 0
    G

    It is stated in the problem that the given input array has this property: num[i] ≠ num[i+1], so your case would be impossible.


Log in to reply
 

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