Java Binary Search Solution Showing Each Possible Condition.


  • 0
    Y

    O(logn) solution.
    The idea is to use methods similar to binary search.
    Since we only need to return the index to any of the peaks, we can define the binary problem by throwing away either part of the array. Thus the algorithm is showed as following:

    1. Set start = 0 and end = nums.length - 1
    2. find the mid point.
    • If the midpoint is the start or end of the array, compare it with the next or previous element.
    • If the midpoint is in the middle part of the array, compare it with both its previous and next element.
    • If the next element of the midpoint is greater than the midpoint, set start = mid + 1
    • If the previous element of the midpoint is greater than the midpoint, set end = mid - 1.
    1. Loop until start == end. At this point, if the algorithm didn't return during the process, start == end is the point we want.
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        
        int start = 0, end = nums.length - 1;
        
        while (start < end) {
            int mid = start + (end - start) / 2; //prevent overflow
            if (mid == 0 && nums[mid] > nums[mid + 1] || mid == nums.length - 1 && nums[mid] > nums[mid - 1]) {
                return mid;
            } else if (mid != 0 && mid != nums.length - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (mid != nums.length - 1 && nums[mid] < nums[mid + 1]) {
                start = mid + 1;
            } else if (mid != 0 && nums[mid] < nums[mid - 1]) {
                end = mid - 1;
            }
        }
        
        return start;
    }
    

Log in to reply
 

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