[java/0ms] Binary search on local peak


  • 2

    First, glad to know that nums[i] != nums[i+1], otherwise there are much more labor work to do.

    Second, you can only use local peak, that is, you can only use relationship of num[mid] and nums[mid+1] to tell whether there's a local peak exist. If you use nums[low] or nums[high] compared with nums[mid], you can't guarantee a global peak exist. However, you can use nums[0] or nums[nums.length-1] to guarantee a global peek.

    public int findPeakElement(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
            int low = 0, high = nums.length-1;
            while (low < high) {
                int mid = (high - low) / 2 + low;
                // local peak exist on left
                if (nums[mid] > nums[mid+1]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    
    

Log in to reply
 

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