Binary search solution


  • 5
    D

    My binary search solution:

    public int findPeakElement(int[] num) {
        int n = num.length;
        if (n <= 1) return 0;
        // handle the first and last element in num[]
        if (num[0] > num[1]) return 0;
        if (num[n - 1] > num[n - 2]) return n - 1;
        int left = 1, right = n - 2;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {
                return mid;
            } else if (num[mid] > num[mid + 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

  • 0
    X

    When no peak is found, the last "return left" statement is problematic, you might want to return an error code instead of the last "left".


  • 0
    D

    My answer was accepted. So I think there must be one and only one peek in the array num[]. You can look at my answer to this question.


  • 0
    D

    My answer was accepted. So I think there must be one and only one peek in the array num[].
    If you try to return an error code such as -1, then the solution will be wrong answer. In this case [1,2,1], we get -1, but the excepted answer is 1.
    But I can modify my solution like this:

    public int findPeakElement(int[] num) {
        int n = num.length;
        if (n <= 1) return 0;
        // handle the first and last element in num[]
        if (num[0] > num[1]) return 0;
        if (num[n - 1] > num[n - 2]) return n - 1;
        int left = 1, right = n - 2;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) {
                return mid;
            } else if (num[mid] > num[mid + 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    

    This is also accepted. But you can confirm that the last return statement is never executed in all of the cases.


  • 0
    X

    why the peak element should be the middle and if not it will be in either left part or right part?


  • 0
    P

    The original code is correct: if the peak is either returned inside the loop or represented by the left when the loop is ended.


  • 0
    N

    have you test [1, 2, 1, 1, 1, 1, 1, 1, 1]


Log in to reply
 

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